29.三数之和

题目

给你一个整数数组 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

思路

特判，对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回 []。

这道题有两个关键点的要求:

如何高效的找到三个数: 暴力三重循环是O(n²)，会超时。
如何去重: 同一个三元组不能出现多次(即使数字位置不同)

最优解法: 排序 + 双指针

先把数组排序(这是去重和双指针的前提)
固定第一个数nums[i]，问题转化为: 在i右边的区间里找两个数，使他们的和等于 -numsi
对于两数之和，在有序数组中可以用双指针: 左指针left从i + 1出发，右指针right从末尾出发
- 若三数之和 > 0，说明太大，right --
- 若三数之和 < 0，说明太小，left ++
- 若三数之和 = 0，记录答案，然后双指针同时向中间收缩。

为什么要排序后使用双指针？

排序后数组单调递增。
固定i后，left右移会让和增大，right左移会让和减小。

所以我们能根据当前和与0的大小关系，定性的移动指针，把复杂度从O(n²)降到O(n)

去重的三个关键点

这是最容易出错的地方，必须要处理三处去重:

固定数i的去重: 如果nums[i] == nums[i - 1]，跳过。注意是和前一个比较，不是后一个(否则会漏解，比如[-1, -1, 2]，中第一个-1必须保留)
- 我们要保留一组相同值里的第一个（它右边的搜索空间最完整）。
  - 「和前一个 (i-1) 比较」= 保留第一个，跳过后续；
  - 「和后一个 (i+1) 比较」= 跳过第一个，保留最后一个 → 漏解。
  - 特别注意 [-1, -1, 2] 这种「解里本来就有重复值」的情况有人会担心：「我跳过重复的 -1，那 [-1, -1, 2] 里的两个 -1 不就没了吗？」
  - 不会。因为：
  - 固定数 i 只用第一个 -1（去重作用在这一层）；
  - 第二个 -1 是由 left 指针找到的，它在双指针搜索阶段，不受固定数去重影响。
  - 所以 i=0 固定第一个 -1，left 找到第二个 -1，right 找到 2，完美组成 [-1, -1, 2]。去重和「解内允许重复值」这两件事发生在不同的层级，互不冲突。
左指针left的去重: 找到一组解后，left右移时跳过相同的值
右指针right的去重: 找到一组解后，right左移时跳过相同的值

剪枝优化

排序后若nums[i] > 0，由于后面的数都 >= nums[i]，肯定都大于0，三数之和不可能为0，直接break。

class Solution {
    fun threeSum(nums: IntArray): List<List<Int>> {
        val result = ArrayList<List<Int>>()
        val size = nums.size

        if (nums.size < 3) {
            return result
        }
        nums.sort()


        for (i in nums.indices) {
            // 剪枝：最小的数已经 > 0，后面不可能凑出和为 0，直接break
            if (nums[i] > 0) {
                break
            }

            // 对固定数去重：跳过与前一个相同的值（注意是 i-1，不是 i+1）
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue
            }
            val target = - nums[i]

            var left = i + 1
            var right = size - 1

            while (left < right) {
                val sum = nums[left] + nums[right]
                if (sum == target) {
                    result.add(listOf(nums[i], nums[left], nums[right]))

                    // 左指针去重
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++
                    }
                    // 右指针去重
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--
                    }

                    // 收缩双指针，继续寻找下一组
                    left++
                    right--
                } else if (sum < target) {
                    left ++
                } else {
                    right --
                }
            }
        }

        return result
    }
}


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        if not nums or len(nums) < 3:
            return res
        nums = sorted(nums)
        for i in range(len(nums) - 2):
            if nums[i] > 0:
                return res
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            left = i + 1
            right = len(nums) - 1
            while left < right:
                result = nums[i] + nums[left] + nums[right]
                if result > 0:
                    # 需要right减小
                    right -= 1
                elif result < 0:
                    left += 1
                else:
                    res.append([nums[i], nums[left], nums[right]])
                    # 去重复，判断左边或右边的元素是否与当前的相同，相同就夸脱
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1

                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                     # 移动指针
                    left += 1
                    right -= 1
        return res

复杂度分析:

时间复杂度：O(n²)，数组排序 O(NlogN)，遍历数组 O(n)，双指针遍历 O(n)，总体 O(NlogN)+O(n)∗O(n)，O(n²)
空间复杂度：O(1)
下一题

邮箱：charon.chui@gmail.com
Good Luck!