题目描述：

重点：与两数之和不同，两数之和只用返回一个下标组合，三数之和是返回所有元素组合，且不重复

方法1：使用双指针，对数组排序后，i 从0遍历到 n-3，左指针是 i+1，右指针是 n-1，然后记得去重

• 如果nums[i]大于0，返回结果

• 如果nums[i] + nums[left]大于0，遍历下一个i

• if(i>0 && nums[i] == nums[i-1]) continue，不能是nums[i] == nums[i+1]，不然（-1，-1，2）过不了

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> result;
        sort(nums.begin(),nums.end());

        for(int i=0;i<n-2;i++){
            int left = i+1;
            int right = n-1;
            if(nums[i] > 0) return result;
            if(i>0 && nums[i] == nums[i-1]) continue;
            while(left < right){
                while(left<right && nums[left] == nums[left+1]) left++;
                while(left<right && nums[right] == nums[right-1]) right--;
                if(nums[i] + nums[left] > 0) break;
                int sum = nums[i] + nums[left] + nums[right];

                if(sum > 0) right--;
                else if(sum < 0) left++;
                else {
                    result.push_back({nums[i],nums[left],nums[right]});
                    left++;
                    right--;
                }       
            }         
        }
        return result;
    }
};

出现错误，[-19,-5,-5,10,12]过不了，left是-5的时候，会+1，导致right不能取到-5，所以while去重应该放存结果的下一行

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> result;
        sort(nums.begin(),nums.end());

        for(int i=0;i<n-2;i++){
            int left = i+1;
            int right = n-1;
            if(nums[i] > 0) return result;
            if(i>0 && nums[i] == nums[i-1]) continue;
            while(left < right){
                if(nums[i] + nums[left] > 0) break;
                int sum = nums[i] + nums[left] + nums[right];

                if(sum > 0) right--;
                else if(sum < 0) left++;
                else {
                    result.push_back({nums[i],nums[left],nums[right]});
                    while(left<right && nums[left] == nums[left+1]) left++;
                    while(left<right && nums[right] == nums[right-1]) right--;
                    left++;
                    right--;
                    
                }       
            }         
        }
        return result;
    }
};

或者

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> result;
        sort(nums.begin(),nums.end());

        for(int i=0;i<n-2;i++){
            int left = i+1;
            int right = n-1;
            if(nums[i] > 0) return result;
            if(i>0 && nums[i] == nums[i-1]) continue;
            while(left < right){
                if(nums[i] + nums[left] > 0) break;
                int sum = nums[i] + nums[left] + nums[right];

                if(sum > 0) right--;
                else if(sum < 0) left++;
                else {
                    result.push_back({nums[i],nums[left],nums[right]});
                    
                    left++;
                    right--;
                    while(left<right && nums[left] == nums[left-1]) left++;
                    while(left<right && nums[right] == nums[right+1]) right--;
                    
                }       
            }         
        }
        return result;
    }
};

注：先找到，然后再移！