题解 | #三数之和#

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<int>B;
        vector<vector<int> >A;
        if(num.size()<3)
            return A;
        //先给数组num从小到大排序
        sort(num.begin(), num.end());//排序
        for(int i=0;i<num.size()-2;i++){
            //每次都假设当前的数作为a
            if(i==0||num[i]!=num[i-1]){//保证这个三元组不重复的第一个条件
                int target=-num[i];
                //只要在i往后找两个数的和等于target即可
                int left=i+1;int right=num.size()-1;
                while(left<right){
                    if(num[left]+num[right]<target){
                        left++;
                    }
                    else if(num[left]+num[right]>target)
                        right--;
                    else{//此时num[left]+num[right]==target,但是要防止重复
                        if(left==i+1||num[left]!=num[left-1]){//不是重复的
                            B.push_back(num[i]);
                            B.push_back(num[left]);
                            B.push_back(num[right]);
                            A.push_back(B);
                            B.clear();
                        }
                        left++;
                        right--;
                    }
                }
            }
        }
        return A;
    }
};