求数组中和为零的不重复三元组。

核心回答

先排序，再固定第一个数，用左右双指针在其右侧寻找另外两个数，时间复杂度为 O(n²)。去重的是三元组的数值组合，不是禁止三元组中出现相同数值；例如 [-1, -1, 2] 合法，但必须来自三个不同位置。

排序后，固定 a[i]，令 left = i + 1、right = n - 1。三数之和小于 0 就右移左指针，大于 0 就左移右指针，等于 0 则收录并跳过左右重复值。外层也要跳过已经作为首元素处理过的值。

下面返回数值三元组，并通过排序副本保留原数组。除结果外的额外空间为 O(n)，不能把整个 Python 实现说成 O(1) 空间。

Python 实现

def three_sum(nums: list[int]) -> list[list[int]]:
    a = sorted(nums)
    result = []

    for i in range(len(a) - 2):
        if i > 0 and a[i] == a[i - 1]:
            continue
        if a[i] > 0:
            break

        left, right = i + 1, len(a) - 1
        while left < right:
            total = a[i] + a[left] + a[right]
            if total < 0:
                left += 1
            elif total > 0:
                right -= 1
            else:
                result.append([a[i], a[left], a[right]])
                left += 1
                right -= 1
                while left < right and a[left] == a[left - 1]:
                    left += 1
                while left < right and a[right] == a[right + 1]:
                    right -= 1

    return result

例如输入 [-1, 0, 1, 2, -1, -4]，返回 [[-1, -1, 2], [-1, 0, 1]]。结果中的每组按升序排列；题目通常不要求各组的返回顺序。

为什么移动指针不会漏解？

固定首元素后，只需在有序区间内寻找和为 -a[i] 的一对数。

若当前三数和小于 0，当前左值搭配区间内最大的右值都不够，换成更小的右值也不会得到 0。因此可以排除当前左值，将 left 右移。三数和大于 0 时对称：当前右值即便搭配区间内最小的左值也过大，可以将 right 左移。

找到一组后，固定首元素和左值就已经决定了所需的右值。再次使用相同左值或右值只能得到重复组合，跳过它们不会漏掉新的数值组合。指针不断收缩，每个首元素对应的扫描都是线性的。

i < left < right 还保证三个位置互不相同。排序会改变位置顺序，但不会让同一个元素被使用两次。

去重为什么要分两层？

**第一层，跳过已经处理过的首元素。**判断的是 a[i] == a[i - 1]。例如 [-1, -1, 2]，第一次固定 -1 时仍可在右侧使用第二个 -1；下一次再固定相同首值才跳过。若一开始就因为当前值等于下一个而跳过，会漏掉这组答案。

**第二层，找到答案后跳过相同左右值。**例如 [0, 0, 0, 0]，应得到一组 [0, 0, 0]。先记录答案，再收缩并跳过重复值，不会把有效的三个 0 提前全部删掉。

去重不是先对整个数组做集合转换。这样会丢失重复次数，让 [-1, -1, 2]、[0, 0, 0] 等答案无法构成。

复杂度和容易遗漏的边界

排序需要 O(n log n) 时间。外层最多 O(n) 次，每次双指针只向中间移动，总计 O(n)，所以整体为 O(n²)。内层虽然有跳过重复值的循环，指针仍只沿一个方向移动，不会多出一层 O(n)。

这份实现用 sorted 创建长度为 n 的新列表，因而额外空间为 O(n)，再加返回结果的 O(k) 空间，k 是答案数量。双指针本身只用常数空间；即使改成 nums.sort()，仍应按具体排序实现考虑辅助空间。

可优先检查：

• 少于三个元素：返回空列表，代码也能处理。
• [0, 0, 0, 0]：只返回一组 [0, 0, 0]。
• [-1, -1, 2]：允许重复值，不能提前删重。
• [-2, 0, 0, 2, 2]：只返回一组 [-2, 0, 2]。
• 全正数、全负数或没有合适组合：返回空列表。

a[i] > 0 才能直接结束，因为它右侧的数不会更小；不能写成 a[i] >= 0，否则会漏掉三个 0。若使用有固定整数宽度的语言，还应根据输入范围决定求和是否需要更宽类型。

常见追问

如果要求返回原数组下标呢？

需要在排序时保留原下标，或设计带索引的哈希方案，并重新说明去重要求：数值组合去重与枚举不同下标组合不是同一个目标。不能把排序后的下标直接当作原下标。

能否固定一个数，再用哈希找另外两个？

可以做到期望 O(n²)，但要另外处理不同位置、重复次数和组合去重。排序双指针能把单调移动与去重结合起来，因此这道题更容易解释和实现；不能据此断言哈希方法一定更慢。

参考资料