三数之和

题目描述

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

输入输出样例

Input: [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

  在这个样例中，可以组成零的三元组有[[-1,-1,2],[-1,0,1],[-1,0,1]],但是题目要求去重，所以最后只可以保留[[-1,-1,2],[-1,0,1]];

题解

  三个值的计算可能会比较麻烦，但是固定一个值，仅去计算两数之和就会简单很多。我们可以先对数组进行一个排序，方便待会儿处理左右指针的移动。至于固定一个值，我们可以使用for循环,使用完一个推向下一个。
  由于存在数字重复,所以需要对数字进行去重。在固定好第一个值后，我们就要开始操作双指针了。i是值固定，因此我们的left必须为(i+1),right不受影响也就是数组的最后一个值(len-1)。因为$a+b+c=0$,所以$a+b=-c$，接下来就是通过值的比较来寻找有效三元组。

  当找到一个有效三元组时，left与right需同时变化。这里仍需考虑去重问题如:[-1,-1,-1,3,3,3];left = 1,right =4;，为了避免这种情况,我们需要对数字进行去重。最后重复前面操作就可以得出结果了，具体代码如下：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // base case
        int len = nums.size();
        if (len < 3) return{};

        // save result
        vector<vector<int> > res;
        std::sort(nums.begin(),nums.end());

        //固定一个值
        for (int i = 0;i < len; i++) {
            //第一个值大于零，则直接返回
            if (nums[i] > 0) return res;

            // 去重
            if (i > 0 && nums[i] == nums[i-1]) continue;

            //双指针操作
            // left起始点在i之后，right 不受影响
            int left = i + 1, right = len -1;
            while (left < right) {  
                int sum = nums[left] + nums[right];
                if (sum > -nums[i]) right--;
                else if (sum < -nums[i]) left++;
                else {
                    //找到一个有效三元组
                    res.push_back({nums[i],nums[left],nums[right]});
                    left++;
                    right--;
                    
                    //去重
                    while (left < right && nums[left] == nums[left-1]) left++;
                    while (right < right && nums[right] == nums[right+1]) right--;
                }
            }
        }
        return res;
    }
};