15三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例 2：

输入：nums = []
输出：[]

示例 3：

输入：nums = [0]
输出：[]

提示：

• 0 <= nums.length <= 3000
• `-105 <= nums[i] <= 105

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans={};
        sort(nums.begin(),nums.end());
        //a=nums[i]  b=nums[left]  c=nums[right]
        for(int i=0;i<nums.size();i++){
            if(nums[i]>0) return ans; //往后所有都是正数就可以break了
            if(i>0&&nums[i]==nums[i-1]) continue;//不能跳过前面一个
            int left=i+1;
            int right=nums.size()-1;
            while (right>left)
            {
               int sum=nums[i]+nums[left]+nums[right];
               if(sum>0) right--;
               else if(sum<0) left++;
               else{
                   vector<int>tem={nums[i],nums[left],nums[right]};
                   ans.push_back(tem);
                   //left和right去重，右移到非重复数据
                   while ((left<right)&&(nums[left]==nums[left+1])) left++;
                   while((left<right)&&(nums[right]==nums[right-1])) right--;
                //只有找到答案的时候才一起收缩,放在外面就收缩两次了
                left++;
                right--;
               }
            }
        }
        return ans;
    }
};