第15题. 三数之和

第15题. 三数之和

力扣题目链接(opens new window)

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

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

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

//双指针
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>>result;
        sort(nums.begin(),nums.end());
        for(int i=0;i < nums.size();i++){
            if(nums[i] > 0){
                return result;
            }
            if(i > 0 &&nums[i]==nums[i-1]){
                continue;//去重a
            }
            int left = i+1;
            int right = nums.size()-1;
            while(left<right){
            if(nums[i]+nums[left]+nums[right] > 0){right--;}
            else if(nums[i]+nums[left]+nums[right] < 0){left++;}
            else{//找到b,c
                result.push_back(vector<int>{nums[i],nums[left],nums[right]});//收集
                while(left<right&&nums[left]==nums[left+1]){//去重b
                    left++;
                }
                while(left<right&&nums[right]==nums[right-1]){//去重c
                    right--;
                }
                //找到答案，俩指针同时收缩
                right--;
                left++;
            }
            }
        }
        return result;
    }
};