题解 | #数组中相加和为0的三元组#

1. 注意先直接排序。
2. 注意三个指针的遍历。
3. sort的时间复杂度是 nlogn
4. 注意中途的剪枝操作，可以避免重复的结果，加快搜索速度。
5. 注意和最小位的相反数相等的原则。

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int> > result;

        if(num.size()<3){
            return result;
        }

        sort(num.begin(),num.end());// n(logn)

        for(int i = 0; i< num.size()-2;i++){
            if(num[i] == num[i-1]&&i) continue;//去重复，主要是第二个元素开始有重复的情况

            int l = i+1, r = num.size()-1;

            while(l<r){
                if(num[l]+num[r]==-num[i]){
                    result.push_back({num[i],num[l],num[r]});

                    //优化
                    while(num[l] == num[l+1]&&l+1<r) l++;//i不变去重复 主要是l
                    while(num[r] == num[r-1]&&l<r-1) r--;//i不变去重复 主要是r

                    l++;
                    r--;

                }else if(num[l]+num[r]>-num[i]){
                    r--;
                }else{
                    l++;
                }
            }

        }



        return result;


    }
};