BM54　三数之和¶

中等通过率 22.68%python3核心代码模式样例通过牛客 AC数组排序双指针

牛客原题　源码

讲解章节：双指针与滑动窗口

一句话

排序后固定最小的数，另外两个用左右双指针夹逼，三处跳重。

解题思路¶

这题考什么¶

排序是这题的总开关，一次排序同时解决三件事：三元组内部自动非降序、相同元素挨在一起便于跳过、有序数组才能用双指针单调夹逼。

主体是「固定一个 + 双指针」：

for i in 0 .. n-3:              固定最小的数 num[i]
    left = i + 1, right = n - 1
    while left < right:
        s = num[i] + num[left] + num[right]
        s == 0   记账，然后两个指针同时内移并跳过重复
        s <  0   和偏小，只能把小的一端抬高  ->  left 加一
        s >  0   和偏大，只能把大的一端压低  ->  right 减一

双指针不会漏解：数组有序，s < 0 时把 right 左移只会让和更小，那一列组合整体可以安全排除；s > 0 对称。每轮至少有一个指针移动，内层是 O(n)，配上外层的 O(n) 共 O(n 的平方)。双指针的通用套路见双指针与滑动窗口。

数据规模与复杂度¶

0 <= n <= 1000，元素取值 |val| <= 100，时限其他语言 2 秒。排序 O(n log n) 加主体 O(n 的平方) = 1e6 次基本操作，Python 下零点几秒。三重循环枚举是 1e9 次，判题机比本机还慢数倍，必然超时。空间：sorted 另建一份长度 n 的列表，O(n)，题面允许到 O(n 的平方)。

坑在哪¶

三元组内部必须非降序（题面注意事项第一条 a <= b <= c）。排序后按 i < left < right 取值天然满足；换成哈希凑数的写法还得对每组结果单独排序，且去重更难写。
三处跳重缺一不可，牛客严格比对，多出一份重复三元组就是错：外层不跳，[0,0,0,0] 会输出两份 [0,0,0]；命中后不跳 left 与 right，[-2,0,0,2,2] 会把 [-2,0,2] 输出两次。
命中后两个指针必须同时移动。只移一个的话，和必然偏离 0，虽不至于出错但白跑一轮；两个都不动就是死循环。
剪枝用 break 而不是 continue：排序后 num[i] > 0 意味着后面的 i 只会更大，三个正数的和不可能为 0，整个外层可以直接结束。
解集本身的顺序也参与比对。外层 i 递增、内层 left 递增，产出的结果集恰好是字典序升序，不需要也不应该再排一次。
n < 3 时 range(n - 2) 为空（n = 0 时是 range(-2)，同样为空），直接返回空列表，示例 1 的 [0] 正是这种输入。

样例复核¶

[-10, 0, 10, 20, -10, -40]，排序后 [-40, -10, -10, 0, 10, 20]。

i=0 (-40)  双指针从两端夹到相遇，找不到配对
i=1 (-10)  依次找到 (-10, -10, 20) 与 (-10, 0, 10)
i=2 (-10)  与前一个相同，被外层跳重挡下

输出 [[-10,-10,20], [-10,0,10]]，与题面给出的解集一致。

参考实现¶

solutions/nowcoder/BM54/sol.py
from typing import List, Optional


class Solution:
    def threeSum(self, num: List[int]) -> List[List[int]]:
        num = sorted(num)               # 排序：三元组自动非降序，重复元素相邻
        n = len(num)
        res = []
        # 外层固定三元组里最小的那个数，右边至少要留两个位置给双指针
        for i in range(n - 2):
            if num[i] > 0:
                break                   # 最小的都为正，后面的 i 更大，整个外层可以收工
            if i > 0 and num[i] == num[i - 1]:
                continue                # 去重点 1：同一个最小值只枚举一次
            # 双指针只在 i 右侧的区间里夹逼，保证下标严格递增、取值非降序
            left, right = i + 1, n - 1
            while left < right:
                s = num[i] + num[left] + num[right]
                # 有序数组保证：和偏小只能抬左端，和偏大只能压右端，被排除的组合不含答案
                if s == 0:
                    res.append([num[i], num[left], num[right]])
                    # 命中后先跳过两端的重复值，再各自内移一格，否则同一组答案会重复记账
                    while left < right and num[left] == num[left + 1]:
                        left += 1       # 去重点 2：左端跳过相同的值
                    while left < right and num[right] == num[right - 1]:
                        right -= 1      # 去重点 3：右端跳过相同的值
                    left += 1           # 记账完毕，两端同时内移换下一组候选
                    right -= 1
                elif s < 0:
                    left += 1           # 和偏小，抬高小的一端
                else:
                    right -= 1          # 和偏大，压低大的一端
        return res

BM54 三数之和¶