LeetCode-hot100系列15-3sum2sum排序双指针

jiezi

5 年前

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c，使得 a + b + c = 0？找出所有满足条件且不重复的三元组。

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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：

[[-1, 0, 1],
  [-1, -1, 2]
]

算法题的基本原则，先从暴力法开始，这里的 3sum，用暴力法的伪代码如下

for(int i = 0; i < nums.length; i++) {for(int j = i + 1; j < nums.length; j++) {for(int k = j + 1; k < nums.length; k++) {if(nums[i] + nums[j] + nums[k] == 0) {record_trip;}
        }
    }
}

可以看出复杂度是

$$
O(n^3)
$$

遇到 3sum 的时候，会想到类似的 2sum 问题，那个题的暴力解法也是 O(n^2)的遍历，优化解法是利用 hash 登记 + 一层循环 来解决。考虑到 3sum 也可以有类似的解题思路（这里是基于了 2sum 的经验）。

3sum 问题考虑用 两层循环 +hash 登记 ，两层循环记录两两数字的和，然后得到它们需要的数字，
遍历到每个数字的时候都去查表：

如果 hash 里 found=null，说明没有登记过，说明没有二元组需要它
如果 hash 里 found=true，说明已经成功匹配过了
如果 hash 里 found=false，说明刚好有二元组需要该元素

大体思路如上，但是为了处理去重逻辑需要做很多判断，时间复杂度 O(n^2)

网上的解题思路看到的方法，既然 2sum 处理起去重问题比较棘手，并且复杂度也才 O(n^2)时，去重 –> 排序 是一个非常重要的思路，需要去重的时候往往排序后会比较好处理 （源自于编码工作以及 linux sort -nr 等经验带来的直觉）
于是，先用复杂度

$$
O(logn)
$$

的快排将数组排序

这时候 3sum 的三个数（min,mid,max）具有这样的关系：

最小的数一定在最左边，其余两个数在它的右边。自然而然想到在最小数的右边最小最大位置各安插一个指针来双指针法找结果（算法的直觉，有排序属性存在，就不可能用 O(n^2)去两两遍历剩下的数，自然而然想到双指针）
如上图的 - 1 和 -1，当前遍历的位置 - 1 如果发现前一个也是 - 1 的时候，为了去重，就可以直接 pass 当前循环
如果最小的 min 已经是正数了，另外两个会更大，则不可能会有结果了，直接结束方法

class Solution {public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++) {if(i > 0 && nums[i] == nums[i-1]) {continue; // 和前一个相等，则跳过，去重}
            if(nums[i] > 0) {return res; // nums[i]是三个数里面最小的，它都大于 0 了，就不可能和为零了
            }
            int require = nums[i] * -1;
            int l = i + 1;
            int r = nums.length-1;
            while(l < r) {
                // l 或 r 如果和上一个重复了，则跳过，为了去重
                if(l - 1 > i && nums[l-1] == nums[l]) {
                    l++;
                    continue;
                }
                if(r + 1 < nums.length && nums[r+1] == nums[r]) {
                    r--;
                    continue;
                }
                // 和 require 比较，并且调整 l 和 r
                if(nums[l] + nums[r] < require) {
                    l++;
                    continue;
                }
                if(nums[l] + nums[r] > require) {
                    r--;
                    continue;
                }
                if(nums[l] + nums[r] == require) {List<Integer> list = Arrays.asList(nums[i], nums[l], nums[r]);
                    res.add(list);
                    l++;
                    r--;
                    continue;
                }
            }
        }
        return res;
    }
}

先用暴力法保底，2sum 其实是最容易想到优化方法，但是处理去重问题逻辑太麻烦，
因为去重而想到了排序，进而用到了 双指针

算法题有时需要根据过往刷题的 经验 -> 直觉 来解决问题的，例如去重想到排序，排序后找 mid 和 max 用到双指针

LeetCode-hot100系列15-3sum2sum排序双指针

题目描述

思路分析

暴力法

转为 2sum 问题

排序 + 双指针法

代码实现

总结