【LC100】No15. 三数之和

题目描述

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

提示：

• 3 <= nums.length <= 3000

• -105 <= nums[i] <= 105

示例

示例 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 。

链接

思路

本题在示例中有一个提示点：输出的顺序和三元组的顺序并不重要。据此，提示我们可以先进行排序。

而本题的难点在于：答案中不可以包含重复的三元组。这意味着，我们要么在寻找时就去除重复项，要么多加几步单独处理重复项。

解法一：哈希表暴力法

《嗯做法》

普通暴力法需要三层循环，可以借鉴普通两数之和的哈希表降维处理。

哈希表中存储 ( 0 - nums[i], i )，便于直接拿取。

关于去重，将找到的三个数按顺序排列后，存入 set 中，最后将 set 转化为 list 返回。

代码

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> res = new HashSet<>();
        Map<Integer, Integer> diffMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            diffMap.put(0 - nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int sum = nums[i] + nums[j];
                if (diffMap.containsKey(sum) && diffMap.get(sum) != i && diffMap.get(sum) != j) {
                    List<Integer> list = new ArrayList<>(Arrays.asList(nums[i], nums[j], 0 - sum));
                    Collections.sort(list);
                    res.add(list);
                }
            }
        }
        return res.stream().collect(Collectors.toList());
    }
}

• 时间复杂度：O(n²)

• 空间复杂度：O(n²)

解法二：双指针法

非常精彩的一个解法！

返回的结果不要求顺序，我们可以联想到排序。

经过排序，题目和 https://tiamo495.com/archives/lc100-no167.-liang-shu-zhi-he-ii---shu-ru-you-xu-shu-zu 类似。

通过固定第一个数，之后寻找合适的第二个数和第三个数的方法降维后，我们同样可以使用双指针来处理。

在这个解法中有几个很巧妙的处理：

1. 经过排序后，在三个数字依次寻找的过程中，当遇到和前一个数相等的数字，可以直接跳过本次循环，进行下一次。

2. 非递减排序后，如果 nums[i] 和下一个数 nums[i+1] 和 下下一个数 nums[i+2] 相加的和大于 0，代表最小的三个数相加都比 0 大。后面不可能有正确答案，可以直接结束本次循环。

3. 同样，非递减排序后，如果 nums[i] 和最右边末尾的两个数相加的和小于 0，代表固定 nums[i]，另外两个数取最大时和都比 0 小，意味着 nums[i] 太小了。此时也无法找到正确答案，可以结束对 nums[i] 的处理，继续处理下一个数。

代码

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 - 2; i++) {
            // 巧妙点1：对于第一个数，跳过相同数字
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            // 巧妙点2：最小的三个数和大于0，结束所有循环
            if (nums[i] + nums[i + 1] + nums[i + 2] > 0) {
                break;
            }
            // 巧妙点3：最小数和最大的两个数，三个数和小于0，结束对于nums[i]的处理
            if (nums[i] + nums[nums.length - 1] + nums[nums.length - 2] < 0) {
                continue;
            }
            // 在i的右侧开始使用双指针找数字
            int j = i + 1;
            int k = nums.length - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum < 0) {
                    // 小于0，较小的数太小了，右移
                    j++;
                } else if (sum > 0) {
                    // 大于0，较大的数太大了，左移
                    k--;
                } else {
                    // 找到了，将三个数存入结果list中
                    res.add(List.of(nums[i], nums[j], nums[k]));
                    j++;
                    // 巧妙点1：对于第二个数，也跳过相同的数字
                    while (j < k && nums[j] == nums[j - 1]) {
                        j++;
                    }
                    k--;
                    // 巧妙点1：对于第三个数，也跳过相同的数字
                    while (k > j && nums[k] == nums[k + 1]) {
                        k--;
                    }
                }
            }
        }
        return res;
    }
}

• 时间复杂度：O(n²)

• 空间复杂度：O(1)