Leetcode15. 3Sum

ddddLeetcode刷题

• Author：李英民 | Henry
• E-mail: li_yingmin@outlookdotcom
• $Beijing~~U~of~Posts~and~Telecom$$(BUPT~)$
• Home: https://liyingmin.wixsite.com/henry

• 快速了解我: About Me

• 转载请保留上述引用内容，谢谢配合！

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

我的代码：

//Author: Li-Yingmin@https://liyingmin.wixsite.com/henry
//Email: li_yingmin@outlook.com
//Leetcode-15
//T(n)=O(n^2), S(n)=O(1)
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) 
    {
        if(nums.size() < 3) return vector<vector<int>>();
        vector<vector<int>> result;
        //排序
        sort(nums.begin(),nums.end());
        auto vbeg = nums.begin();
        auto vend = nums.end();
        constexpr int target = 0;
        for(auto indexi = vbeg ; indexi < vend - 2; ++indexi)
        {
            if(3*(*indexi) > target) break;//见分析
            if(*indexi == *(indexi - 1) && indexi > vbeg) continue;//见分析
            auto indexj = indexi + 1;
            auto indexk = vend - 1;
            while(indexj < indexk)
            {
                if(*indexi + *indexj + *indexk > target)
                {
                    --indexk;
                    while(*indexk == *(indexk + 1) && indexj < indexk) --indexk;
                }
                else if(*indexi + *indexj + *indexk < target)
                {
                    ++indexj;
                    while(*indexj == *(indexj - 1) && indexj < indexk) ++indexj;
                    if(2*(*indexj) > (target - *indexi)) break;
                }
                else //*i + *j + *k = target
                {
                    result.push_back({*indexi,*indexj,*indexk});
                    --indexk;
                    ++indexj;
                    while(*indexj == *(indexj - 1) && indexj < indexk) ++indexj;
                    while(*indexk == *(indexk + 1) && indexj < indexk) --indexk;
                }
            }
        }
        return result;
    }
};

分析：

• 目前已经是最优的答案了，时间复杂度O(n^2)。外层for循环，内层一轮夹逼，所以求解过程复杂度O(n^2)，排序复杂度O(nlogn)。
• 为什么有以下两行代码：

if(3*(*indexi) > target) break;
if(2*(*indexj) > (target - *indexi)) break;

• • 
• if(*indexi == *(indexi - 1) && indexi > vbeg) continue;怎么理解？
• •