三数之和

难点：

• 不可重复
• 优化

思路：

• 因为题目要求三元组不能重复，对于一个无序数组来说，筛选不能重复的三元组是很复杂的，所以我们可以先通过快速排序，然后严格满足i<j<z，假如碰到了与上一个一样的就跳过
• 为了减少复杂度，三层变两层，可以采用双指针，因为当a+b+c==0的时候，b增加指针向右，那c必然减少指针向左

代码：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n=nums.size();
        vector<vector<int>>ans;
        map<int,int>mp;
        sort(nums.begin(),nums.end());
        for(int i=0;i<n;i++){
            if(i>0&&nums[i]==nums[i-1])continue;
            int th=n-1;
            int res=-nums[i];
            for(int j=i+1;j<n;j++){
                if(j>i+1&&nums[j]==nums[j-1])continue;
                while(nums[th]+nums[j]>res&&th>j)th--;
                if(th==j)break;
                if (nums[j] + nums[th] == res) {
                    ans.push_back({nums[i], nums[j], nums[th]});
                }
            }
        }
        return ans;
    }
};