题解 | #三数之和#

W:
首先对数组排序
遍历数组，跳过重复的，保证结果唯一性，后面的用双指针遍历，如图所示；
如果>0 right-- ,<0 left++
如果等于0，同时收缩
N：
同时收缩时需要注意跳过重复的

https://code-thinking.cdn.bcebos.com/gifs/15.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.gif

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int>> res;
        const int len = num.size();
        sort(num.begin(),num.end());

        for(int i=0;i<len;i++){
            if(num[i]>0) {//如果大于0，那么后面肯定没有
                return res;  
            }
            // 错误去重a方法，将会漏掉-1,-1,2 这种情况
            /*
            if (nums[i] == nums[i + 1]) {
                continue;
            }
            */
            if(i>0 && num[i]==num[i-1]){//
                continue;
            }
            int left=i+1,right=len-1;
          while(left<right){
                // 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组
                /*
                while (right > left && nums[right] == nums[right - 1]) right--;
                while (right > left && nums[left] == nums[left + 1]) left++;
                */
              if( num[i] + num[left] + num[right] <0) left++;
              else if( num[i] + num[left] + num[right] > 0) right--;
               else if( num[i] + num[left] + num[right] == 0){

                   res.push_back({num[i] , num[left] , num[right]});
                    while(left< right && num[left+1]==num[left]) left++;
                    while(left< right && num[right-1]==num[right]) right--;

                    right--;
                    left++;
                }

            }
        }
        return res;
    }
};

也可以用set去重，避免许多细节

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int>> res;
        const int len = num.size();
        sort(num.begin(),num.end());
        set<vector<int>> mset;
        for(int i=0;i<len;i++){
            if(num[i]>0) {//如果大于0，那么后面肯定没有
                res.assign(mset.begin(),mset.end());
                return res;  
            }
//             if(i>0 && num[i]==num[i-1]){//
//                 continue;
//             }
            int left=i+1,right=len-1;
          while(left<right){
              if( num[i] + num[left] + num[right] <0) left++;
              else if( num[i] + num[left] + num[right] > 0) right--;
               else if( num[i] + num[left] + num[right] == 0){
                  mset.insert({num[i] , num[left] , num[right]});
//                     while(left< right && num[left+1]==num[left]) left++;
//                     while(left< right && num[right-1]==num[right]) right--;

                    right--;
                    left++;
                }

            }
        }
        res.assign(mset.begin(),mset.end());
        return res;
    }
};