LeetCode 15. 三数之和：排序 + 双指针的教科书示范

三数之和（LeetCode 15）是面试出镜率最高的题目之一，原因不在于它难——而在于它把「找到解」和「找干净解」这两件事分开考：写出 O(n²) 的双指针只是及格线，把重复三元组的排除写得干净利落才是区分度所在。

题面与约束

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

数据范围：3 <= nums.length <= 3000，-10^5 <= nums[i] <= 10^5。3000 的规模意味着 O(n³)（约 270 亿次运算）必然超时，O(n²)（900 万）轻松通过——这个数量级就是题目给的路标。

从暴力到双指针：一次关键的转化

暴力是三重循环 O(n³)。想降维，先注意到一个结构：如果数组是有序的，「两数之和等于定值」可以用双指针在 O(n) 内解决。于是三数之和转化为：固定第一个数 nums[i]，在它右侧的有序区间里找「两数之和 = -nums[i]」。

from typing import List

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        res = []
        n = len(nums)
        for i in range(n - 2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue                      # 去重①：第一个数重复，整轮跳过
            if nums[i] + nums[i + 1] + nums[i + 2] > 0:
                break                         # 剪枝②：最小的三个数都 > 0，后面无解
            if nums[i] + nums[n - 2] + nums[n - 1] < 0:
                continue                      # 剪枝③：当前数配最大两数仍 < 0，i 太小
            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]])
                    while l < r and nums[l] == nums[l + 1]:
                        l += 1                # 去重④：跳过左指针重复值
                    while l < r and nums[r] == nums[r - 1]:
                        r -= 1                # 去重⑤：跳过右指针重复值
                    l += 1
                    r -= 1
        return res

双指针为什么正确：区间有序时，l 右移使和严格变大、r 左移使和严格变小。若当前和 < 0，任何「保住 r」的组合都比当前更小（更不行），所以 l 必须前进；反之亦然——每次移动都安全地排除了一整行或一整列候选，这正是 O(n²) 总复杂度的来源：外层 n 次，内层指针合计只走 O(n) 步。

去重：三数之和的真正考点

题目要求「不重复的三元组」，而排序让相同值聚在一起——于是去重有统一原则：同一层位置的重复值，只允许第一个生效。

• 去重①（外层）：nums[i] == nums[i-1] 时跳过。这个 i 作为「第一个数」能找到的三元组，上一轮 i 已经找全了；
• 去重④⑤（内层）：命中一个三元组后，l 和 r 各自越过所有重复值再继续——否则 [-2, 0, 0, 2] 会输出两次 [-2, 0, 2]；
• 微妙点：外层去重比较的是 nums[i-1]（前一个位置），不是 nums[l]——「值相同但不同位置」的组合在内层是允许的，比如 [-1, -1, 2] 就是合法答案。这也是为什么去重①要从 i > 0 开始判断。

两处剪枝：有序数组的免费午餐

排序不只服务于双指针，还送了两招剪枝：

• nums[i] + nums[i+1] + nums[i+2] > 0 时直接 break——最小的三个数都为正，i 再往后只会更大，整轮无解；
• nums[i] + nums[n-2] + nums[n-1] < 0 时 continue——当前 i 配上最大的两个数都不够 0，这个 i 无解但后面可能有。

在大量随机数据上，这两行能砍掉大半无用的内层循环。我本地用 3000 个随机元素（值域 ±10^5）实测：排序双指针秒级完成，返回的一万多个三元组逐一校验和为零、且无重复。

复杂度

• 时间 O(n²)：排序 O(n log n) + 外层 n × 内层双指针 O(n)；
• 空间 O(log n)（排序递归栈，不计输出）——相比哈希解法还需要额外集合记状态，这个解法原地完成了全部工作。

结语

三数之和的模板可以原样推广：「四数之和」在外面再套一层循环并多一层去重，「最接近的三数之和」把等号比较改成记录最小差值。记住这个骨架——排序定序、外层固定、内层双指针、同层去重——一整族「N 数之和」的题就都有了着落。

参考资料

• LeetCode 15. 三数之和 — 题目页
• LeetCode 官方题解：排序 + 双指针
• 本文全部代码已在本地跑通验证（含 3000 元素压力用例与去重校验）