https://leetcode.cn/problems/3sum/?envType=study-plan-v2&envId=top-100-liked
####双指针，定一选二，需要先对数组进行排序，从小到大
####注意：三元组存储可用结构体，或者直接定义

vector<vector<int>>res //来存储三元组

####不包括重复元素，那么选第一个数的时候，选过之后，后面再出现与之相同的数就直接跳过，在确定第一个数之后，后两个数选择之后碰见相同的也跳过，在第一个数基础上碰见相同的跳过

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
      /*typedef struct thri{
            int x;
            int y;
            int z;
        }T;
    */
    vector<vector<int>>res;
      //  vector<T>res;
        //定一选二
        int n=nums.size();
        sort(nums.begin(),nums.end());//先从小到大排序
        for(int i=0;i<n-2;i++)
            {
                //先列举第一个数的可能情况
            //去重。遇见第一个数相同的就直接跳过
            if (i&&nums[i-1]==nums[i])continue;
            //优化
            if(nums[i]+nums[i+1]+nums[i+2]>0)break;//说明没有能满足的i值了
            if(nums[i]+nums[n-2]+nums[n-1]<0)continue;//说明i太小，要增大
            int left=i+1;
            int right =n-1;//定义左右指针
            while(left<right){
                int s=nums[i]+nums[left]+nums[right];
                if(s>0)right--;
                else if (s<0) left++;
                else{
                    res.push_back({nums[i],nums[left],nums[right]});
                   // 移动左指针, 避免重复解
                    while (left < right && nums[left] == nums[left + 1])left++; //此刻left指向最后一个相同的数的位置
                    left++;
                    // 移动右指针, 避免重复解
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    right--;
                }
            }
            }
        return res;
    }
};