15.三数之和

题目

https://leetcode-cn.com/problems/3sum/

思路

• 固定 3 个指针中最左（最小）数字的指针 i，双指针 left，right 分设在数组索引 (i,nums.size()) 两端，通过双指针交替向中间移动，记录对于每个固定指针 i 的所有满足 nums[k] + nums[i] + nums[j] == 0 的 left,right 组合：
• 当 nums[i] > 0 时直接break跳出：因为 nums[left] >= nums[right] >= nums[i] > 0，即 3 个数字都大于 0 ，在此固定指针 i 之后不可能再找到结果了。
• 当 i > 0且nums[i] == nums[i - 1]时即跳过此元素nums[i]：因为已经将 nums[i - 1] 的所有组合加入到结果中，本次双指针搜索只会得到重复组合。
• left，right 分设在数组索引 (i, nums.size())两端，当left < right时循环计算sum = nums[i] + nums[left] + nums[right]，并按照以下规则执行双指针移动：
  • 当s < 0时，left += 1并跳过所有重复的nums[left]；
  • 当s > 0时，right -= 1并跳过所有重复的nums[right]；
  • 当s == 0时，记录组合[nums[i], nums[left], nums[right]]至res，执行left += 1和right -= 1并跳过所有重复的nums[left]和nums[right]，防止记录到重复组合。

代码

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int target;
        vector<vector<int>> res;
        sort(nums.begin(),nums.end());
        for(int i=0;i<nums.size();i++){
            if(i>0 && nums[i]==nums[i-1]) continue;
            if((target=nums[i])>0) break;
            int left = i+1,right = nums.size()-1;
            while(left < right){
                int sum = nums[i]+nums[left]+nums[right];
                if(sum>0){
                    --right;
                }else if(sum<0){
                    ++left;
                }else{
                    res.push_back({nums[i],nums[left],nums[right]});
                    ++left;
                    --right;
                    while(left< right && nums[left]== nums[left-1]) ++left;
                    while(left< right && nums[right] == nums[right+1]) --right;
                }
            }
        }
        return res;
    }
};