Leetcode 15. 三数之和（排序+双指针）

谁借莪１个温暖的怀抱￠ 2022-10-19 00:56 149阅读 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.com/problems/3sum  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#### 分析(排序+双指针) ####

真心觉得双指针太重要了，双指针分为快慢指针、对撞指针，意思跟名字是一样的。

不过双指针一般需要预先排序，才能发挥其最大作用。

我们首先排个序，然后题目不是求三数之和嘛？ 我们先for循环 每次都确定第一个数暂且叫first，那么这题就与《两题之和》这道题是类似了。

对于剩下的两个数，我们采用对撞指针，即左边一个右边一个，若想满足三数之和为0，那么双指针指向的数值之和应该等于`-first`

如果满足这个条件，add到结果集合中就可以。

需要额外注意的是，本题要求不重复，那么我们在多个地方要进行去重，以应付各种各样的题解，去重的地方如代码注释所示。

#### Java实现 ####

class Solution {
        
        public List<List<Integer>> threeSum(int[] nums) {
        
            List<List<Integer>> result = new ArrayList<>();
            if (nums == null || nums.length < 3) {
        
                return result;
            }
            // 排序 便于去重
            Arrays.sort(nums);
            // 选取第一个数
            for (int i = 0; i < nums.length; i++) {
        
                // 如果大于0，不可能凑起来等于0，因为后面都大于0
                if (nums[i] > 0) {
        
                    continue;
                }
                // 去重
                if (i > 0 && nums[i] == nums[i - 1]) {
        
                    continue;
                }
    
                int target = -nums[i];
                // 找到第一个数，双指针找另外两个数
                int left = i + 1;
                int right = nums.length - 1;
    
                while (left < right) {
        
                    // 若找到剩下两个数
                    if (nums[left] + nums[right] == target  ) {
        
    
                        // 保存结果
                        List<Integer> tmp = new ArrayList<>();
                        tmp.add(nums[i]);
                        tmp.add(nums[left]);
                        tmp.add(nums[right]);
                        result.add(tmp);
                        left++;
                        right--;
                        // 进一步去重，这时是对剩下两个数去重
                        // 保证不越界
                        while(left<right && nums[left]==nums[left-1])
                        {
        
                            left++;
                        }
                        while(left<right &&nums[right]==nums[right+1])
                        {
        
                            right--;
                        }
    				// 需要的和是大于目前的和，所以需要让目前的两个值大一些，由于已排序，让left++就可以
                    } else if (target > (nums[left] + nums[right])) {
        
                        left++;
                    } else {
        
                        right--;// 与前面思想一样
                    }
                }
    
            }
            return result;
        }
    }