LeetCode.015.3Sum 三数之和

题目描述

15 3Sum
https://leetcode-cn.com/problems/3sum/

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

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

示例：

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

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

---

相似题目

LeetCode.001.Two Sum 两数之和
LeetCode.653.Two Sum IV - Input is a BST 两数之和4-输入是BST
LeetCode.532.K-diff Pairs in an Array 数组中的k-diff数对

LeetCode.016.3Sum Closest 最接近的三数之和
LeetCode.015.3Sum 三数之和
18 四数之和
https://leetcode-cn.com/problems/4sum/

---

解题过程

看到这个题可能第一想法是固定一个变量，转化为 2 sum 问题，时间复杂度为 O(n^2)，但难点是三元组判重。
比如全零数组 [0,0,0,0,0,0] ，要么进行特例判断，要么最后再进行判重。

排序+双指针

通过排序解决三元组判重问题，排序复杂度为 O(nlogn)，不会增加最终的算法复杂度，因为至少也需要 O(n^2) 复杂度。
对于三元组 (a, b, c) 只要保证 a <= b <= c，就能保证不重复。
这里的去重包括两方面，对于排序后的数组 nums[]，需要：
1、每层循环 for(int i = 0; i < nums.length; i++) 要保证跳过重复元素，即 nums[i] != nums[i - 1]
2、内层循环的 nums[j] 要大于等于外层循环的 nums[i]，这是为了不重复使用元素。

固定外层循环的 nums[i] 后，内两层循环的 nums[j] 和 nums[k] 是互相制约的关系，因为需要满足 nums[i] + nums[j] + nums[k] == 0，所以 nums[j] 变大时 nums[k] 就必须变小。
利用这个制约关系，我们就可以通过 双指针 把内两层循环变为一层循环，将复杂度降低到 O(n)
左边界 left 从 i + 1 开始，右边界 right 从 nums.length - 1 开始
当 nums[i] + nums[left] + nums[right] < 0 时，只有左边界 left 右移才能增加 三数之和
当 nums[i] + nums[left] + nums[right] > 0 时，只有右边界 right 左移才能减少 三数之和

时间复杂度 O(n^2)，其中排序复杂度为 O(nlogn)
空间复杂度 O(nlogn)，排序需要这些空间复杂度

private static class SolutionV202006 {
    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; // 跳过重复元素
            }
            int left = i + 1;
            int right = nums.length - 1;
            while (left < nums.length && left < right) {
                if (left > i + 1 && nums[left] == nums[left - 1]) {
                    left++;
                    continue; // 跳过重复元素
                }
                if (nums[i] + nums[left] + nums[right] == 0) {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    right--;
                } else if (nums[i] + nums[left] + nums[right] < 0) {
                    // 三数之和比 0 小，左边界 left 右移
                    left++;
                } else {
                    // 三数之和比 0 大，右边界 right 左移
                    right--;
                }
            }
        }
        return res;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_015_3Sum.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_015_3Sum.java

---