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

谁借莪１个温暖的怀抱￠ 2024-03-27 13:06 28阅读 0赞

给你一个整数数组 nums ，判断是否存在三元组 \[nums\[i\], nums\[j\], nums\[k\]\] 满足 i != j、i != k 且 j != k ，同时还满足 nums\[i\] + nums\[j\] + nums\[k\] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

示例 1：

输入：nums = \[-1,0,1,2,-1,-4\]  
输出：\[\[-1,-1,2\],\[-1,0,1\]\]  
解释：  
nums\[0\] + nums\[1\] + nums\[2\] = (-1) + 0 + 1 = 0 。  
nums\[1\] + nums\[2\] + nums\[4\] = 0 + 1 + (-1) = 0 。  
nums\[0\] + nums\[3\] + nums\[4\] = (-1) + 2 + (-1) = 0 。  
不同的三元组是 \[-1,0,1\] 和 \[-1,-1,2\] 。  
注意，输出的顺序和三元组的顺序并不重要。  
示例 2：

输入：nums = \[0,1,1\]  
输出：\[\]  
解释：唯一可能的三元组和不为 0 。  
示例 3：

输入：nums = \[0,0,0\]  
输出：\[\[0,0,0\]\]  
解释：唯一可能的三元组和为 0 。

提示：

3 <= nums.length <= 3000  
\-105 <= nums\[i\] <= 105

## 方法一：排序+双指针 ##

因为题目希望我们找找数字，这时候我们大多时候需要想到双指针这一快速解题思路。而题目的数字顺序是乱序的，按照顺序更方便我们计算，所以要先排序，再进行双指针。其中，详细的是思路是：

*  先选一个元素i作为第一层循环
 *  再让j是i的下一个元素，即保证了i和j的不一样（不包括相同元素情况下），再让k是最后一个元素，即完成了双指针。
 *  j和k移动关系：
    
     *  如果sum>0则意味着比较大则k往左移
     *  如果sum<0则意味着比较小则j往右移

class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            //排序
            Arrays.sort(nums);
            List<List<Integer>> ans = new ArrayList<>();
            int n = nums.length;
            for(int i =0 ; i<n;i++){
                
                if (i>0 && nums[i] == nums[i-1] )continue;
                int j = i+1, k = n-1;
                while(j<k){
                    while(j>i +1 && j < n && nums[j] == nums[j-1]) j++;
                    if(j>=k) break;
                    int sum = nums[i]+ nums[j] +nums[k];
                    if(sum==0){
                        ans.add(Arrays.asList(nums[i],nums[j],nums[k]));
                        j++;
                    }else if(sum>0){
                        k--;
                    }else if(sum<0){
                        j++;
                    }
                
                }
            }
            return ans;
        }
    }

#### 条件作用： ####

让第一层循环选择出来的元素与其下一个元素不同，相同就跳过。就保证了i和j不同

> if (i>0 && nums\[i\] == nums\[i-1\] )continue;

如果没有上述条件，会出现以下

![2f9df54415a4435892c7612f97e79fcd.png][]

#### 原因： ####

排序后数组变成：\[-4,-1,-1,0,1,2\]，如果没有上述条件则会出现两个值一样的

#### 条件作用： ####

保证指针当前数字和下一个数字不同，

> while(j>i +1 && j < n && nums\[j\] == nums\[j-1\]) j++;

如果没有上述条件，会出现以下

![bfc70c48dc4f45cda0a9901296b9f3f0.png][]

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

[2f9df54415a4435892c7612f97e79fcd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/eb76b2aba54a451b8647dc53e2b4f5ae.png
[bfc70c48dc4f45cda0a9901296b9f3f0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/27/d443d8df1e0a4d10822654812c7f028c.png