题解 | #三数之和# 双指针

「不重复」的本质是什么？我们保持三重循环的大框架不变，只需要保证：

• 第二重循环枚举到的元素不小于当前第一重循环枚举到的元素；
• 第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。
• 同时，对于每一重循环而言，相邻两次枚举的元素不能相同

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        sort(num.begin(), num.end());
        int n=num.size();
        if(n<3)
            return {};
        vector<vector<int>> ans;
//         unordered_map<pair<int, pair<int ,int>>, bool> hash;
        // b不等于a
        // c不等于b
        // 同一层循环的不能相等
        for(int i=0; i<n-1; i++)
        {
            if(i>0 && num[i]==num[i-1])
                continue; //去重
            int target=-num[i]; //a+b+c=0 == a+b=-c
            int left=i+1;
            int right=n-1;
            for(left; left<n-1; left++)
            {
                if(left>i+1 && num[left]==num[left-1])
                    continue; //去重
                while(left<right && num[left]+num[right]>target)
                    right--;
                if(left==right) 
                    break;
                if(num[left]+num[right]==target)
                    ans.push_back({num[i], num[left], num[right]});
            }
        }
        return ans;
    }
};