剑指 Offer II 007. 数组中和为 0 的三个数

题目

给定一个包含 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/1fGaJU
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

这道题和昨天的题很像，所以可以先考虑排序。
循环数组获得第一个加数nums[i]，将第一个数固定，这样先找以nums[i]开头的三个数之和为0。
剩下的两个加数和 = -nums[i]，就和昨天的题一样了
初始一个指针left指向i+1,指针right指向最后一个元素。
如果两个加数和+nums[i]>0，说明加数大了,right–
如果两个加数和+nums[i]<0，说明加数小了，left++
如果两个加数和+nums[i]=0，说明找到了第一个以nums[i]开头符合条件的数，需要开始找第二个以nums[i]开头符合条件的数，right–，left++

还需要注意的点是，结果不能重复。
什么时候会重复？
假设[-4,-2a,-2b,0,1,2a,2b] a和b起标识作用。
情况1:后两个加数重复
我们先找到了了第一个[-4,-2a,2b],left++,right–之后，第二个[-4,-2b,2a]又符合条件了，此时结果就会重复。所以当找到一个结果后，就需要跳过与当前nums[left]、nums[right]相同的数。
情况2:第一个加数重复
当我们找到[-2a,0,2b]后，以-2a开头的三个数找完了，那么此时i+1,我们要找以-2b开头的符合条件的三个数。此时就重复了,因为-2开头的在上一轮已经找完了。

var threeSum = function(nums) {
    let len = nums.length;
    if(len<=2)return []; //三数之和，不足三个数的直接返回
    nums.sort((a,b)=>a-b); //先排序
    let res = [];
    for(let i=0;i<len-2;i++){
        if(i>0 && nums[i]==nums[i-1])continue;//排除第一个加数重复的情况
        let left = i+1;
        let right=len-1;
        while(left<right){//昨天的题目解法
            if(nums[left]+nums[right]+nums[i]<0)left++;
            else if (nums[left]+nums[right]+nums[i]>0)right--;
            else{
                res.push([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左侧相等的
                right--;
            } 
           
        }
    }
    return res;
};

最后

以上就是粗心玉米为你收集整理的剑指 Offer II 007. 数组中和为 0 的三个数剑指 Offer II 007. 数组中和为 0 的三个数的全部内容，希望文章能够帮你解决剑指 Offer II 007. 数组中和为 0 的三个数剑指 Offer II 007. 数组中和为 0 的三个数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。