力扣 15 三数之和笔记：重复出在两个地方

题目是给一个整数数组，找出全部和为 0 的三元组，要求下标互不相同，答案里不能有重复的三元组。我先写的是三层循环的笨办法，写完才动手优化。这篇主要记后面去重那一段，重复结果从哪冒出来，我一开始没想明白。

三层循环

任意取三个下标，组合全枚举一遍，和为 0 的收下来。题目不让重复，我直接用集合装排序好的三元组去重：

import itertools

def brute(nums):
    res = set()
    for i, j, k in itertools.combinations(range(len(nums)), 3):
        if nums[i] + nums[j] + nums[k] == 0:
            res.add(tuple(sorted((nums[i], nums[j], nums[k]))))
    return res

官方例子能过：[-1, 0, 1, 2, -1, -4] 得到 [-1, -1, 2] 和 [-1, 0, 1]，[0, 1, 1] 是空，[0, 0, 0] 得到一组 [0, 0, 0]。

n 个数就要跑 C(n, 3) 次循环体。n 取 60 时是 34,220 次，n 到题目上限 3000 时这个数是 4.5×10⁹ 量级，没法交。

固定第一个数

三数之和固定住第一个数，剩下就是在后面的数里找两个，和等于第一个数的相反数。两数之和如果每次还用两层循环，总的复杂度降不下来，所以先把数组排序：排完序，剩下的两数用一左一右两个指针夹。和小于目标，左指针右移把和抬大；和大于目标，右指针左移把和压小。方向能这么定，是因为数组有序。

排序还顺带解决了一半去重问题：相同的值排完会挨在一起，要跳过重复，只需要和相邻位置比。

按这个思路写，结构就是枚举 i，在 i 的右边跑双指针。下面这版是故意没写任何跳过重复的，我拿它测重复到底从哪来。

重复的两个来源

输入 [-2, 0, 0, 2, 2]，没去重的版本输出了两份 [-2, 0, 2]。过程是这样的：第一个数取 -2，左指针停在第一个 0，右指针停在最后一个 2，命中，记下；两个指针各走一步，左指针到了第二个 0，右指针到了前一个 2，还是同样的三个数，又命中一次。

换一组更挤的：[-1, -1, -1, 2, 2] 输出了三份 [-1, -1, 2]。多出来的第三份来源不同：第一个数取到第二个 -1 时，它右边能凑出的组合和取第一个 -1 时完全一样，整个搜索等于重做了一遍。

两处来源，要堵两个地方：

• 第一个数和前一个相同，跳过，不再枚举。
• 命中一组之后，左右指针先把两边相同的数值都跳完，再继续走。

两个地方都补上之后，上面两组输入都只剩一组结果。[0, 0, 0, 0] 也测了，输出一组 [0, 0, 0]。

完整的代码

class Solution:
    def threeSum(self, nums):
        nums.sort()
        res = []
        n = len(nums)
        for i in range(n - 2):
            if nums[i] > 0:
                break
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            l, r = i + 1, n - 1
            while l < r:
                s = nums[i] + nums[l] + nums[r]
                if s < 0:
                    l += 1
                elif s > 0:
                    r -= 1
                else:
                    res.append([nums[i], nums[l], nums[r]])
                    l += 1
                    r -= 1
                    while l < r and nums[l] == nums[l - 1]:
                        l += 1
                    while l < r and nums[r] == nums[r + 1]:
                        r -= 1
        return res

里面还有一个提前结束：排完序后第一个数大于 0，它后面的数只会更大，三个正数凑不出 0，枚举可以直接停。

验证

• 官方三例重测，结果和上面写的一致，另外补了 [0, 0, 0, 0]，只输出一组。
• 随机对拍：数组长度 0 到 9，元素只从 -3 到 3 里取。值域故意压窄，是想让重复元素扎堆，去重逻辑有问题更容易当场暴露。3000 组和三层循环加集合去重的笨办法对照，零失配。
• 计数对比：n = 60 的随机数组，三层循环要跑 34,220 次循环体；双指针这版我数了内层步数，421 步。

复杂度：外层枚举第一个数是 O(n)，每个数配一遍双指针 O(n)，总时间 O(n²)，排序的 O(n log n) 被盖在下面。多用的空间主要是排序本身。