LC15　三数之和¶

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

牛客原题　源码

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

一句话

排序后固定第一个数，剩下两个用相向双指针在有序区间里对撞。

解题思路¶

这题考什么¶

要找出所有和为 0 且互不重复的三元组。三重循环是 O(n^3)， n = 3000 时 2.7e10 次，不可能。

先排序，问题立刻变形：固定最小的那个数 nums[i] 之后，剩下的任务是「在有序数组 nums[i+1 .. n-1] 里找一对和为 -nums[i] 的数」。有序是关键——相向双指针 l、r 可以用 O(n) 解决它：

s = nums[l] + nums[r]
s < 目标  ->  和太小，只能把 l 右移换更大的数（r 左移只会更小）
s > 目标  ->  和太大，只能把 r 左移
s == 目标 ->  记下答案，l 右移且 r 左移，继续找别的组合

每次比较都能确定性地淘汰一个端点，所以内层一趟就够。见双指针与滑动窗口。

排序还顺手解决了去重：相同的值在排序后必然相邻，于是「跳过重复」变成「跳过与前一个相同的元素」这种局部判断，不需要拿 set 存已经产出的三元组（那要对每个三元组做一次哈希，还得把 list 转成 tuple，常数大得多）。

去重要在三个位置各做一次：

外层 i：nums[i] == nums[i-1] 时，以 nums[i] 打头能配出的三元组，上一轮已经全部找过了（候选区间只是少了一个元素，而那个元素等于 nums[i]，真要用到它，上一轮的 l 也能取到）。
内层命中后的 l 与 r：把与刚用过的值相同的位置整段跳过。

数据规模与复杂度¶

3 <= n <= 3000，-1e5 <= nums[i] <= 1e5。排序 O(n log n)，外层 n 轮、每轮内层 O(n)，合计 O(n^2)，约等于 9e6 次基本操作。n = 3000 的随机数据本地实测 0.25 秒，判题机比本机慢数倍，仍有余量。O(n^3) 的三重循环是 2.7e10，差三个数量级。空间除答案外 O(1)（Python 的 sort 是原地的 Timsort）。

坑在哪¶

三处去重缺一不可，而且外层去重必须是 i > 0 and nums[i] == nums[i-1]，不能写成 nums[i] == nums[i+1] 就跳过。后者会把 [0, 0, 0] 这种必须用到重复值的答案整个跳掉——重复值本身是允许出现在同一个三元组里的，不允许的只是同一个三元组被输出两次。
命中之后 l 与 r 必须同时移动。只动一边的话，另一边不变、和必然不再等于目标，虽然不会错但白跑一轮；更糟的是若只动一边又忘了跳重复值，会把同一个三元组反复塞进答案。
跳重复的 while 里要带边界条件 l < r，否则 [0, 0, 0, 0] 这类数据会让 l 冲过 r 越界。
提前剪枝 nums[i] > 0 就 break 是安全的：数组已排序，nums[i] 是三个数里最小的那个，它为正则三数之和必然为正，后面的 i 更不可能凑出 0。这一条把大量正数的数据从 O(n^2) 压到几乎线性。
判题按 unordered_deep 比对，因为题面原文「输出的顺序和三元组的顺序并不重要」——外层三元组之间的先后、以及每个三元组内部三个数的先后都放宽。 顺序放宽不等于内容放宽：同一个三元组吐两次照样判错，所以去重不能省。
没有答案时返回空列表。题面示例 2 的 [0, 1, 1] 就是这种情况， ans 保持初值即可，不必特判。

样例复核¶

nums = [-1, 0, 1, 2, -1, -4]，排序后 [-4, -1, -1, 0, 1, 2]。

i=0  nums[i]=-4  目标 4   l=1 r=5: -1+2=1 <4 -> l=2
                          l=2 r=5: -1+2=1 <4 -> l=3
                          l=3 r=5: 0+2=2  <4 -> l=4
                          l=4 r=5: 1+2=3  <4 -> l=5，l==r 退出
i=1  nums[i]=-1  目标 1   l=2 r=5: -1+2=1 命中 -> [-1,-1,2]
                          跳重复后 l=3 r=4: 0+1=1 命中 -> [-1,0,1]
                          l=4 r=3 退出
i=2  nums[i]=-1 与 nums[1] 相同 -> 跳过（否则会再产出一次 [-1,0,1]）
i=3  nums[i]=0   目标 0   l=4 r=5: 1+2=3 >0 -> r=4，退出
i=4  nums[i]=1 > 0 -> break

得到 [[-1,-1,2], [-1,0,1]]，与样例一致。

参考实现¶

solutions/leetcode/LC15/sol.py
from typing import List, Optional


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 排序是整份解法的地基：它让内层能用相向双指针，也让「相同的值必然相邻」，
        # 去重于是退化成与前一个元素比一下
        nums.sort()
        n = len(nums)
        ans = []
        # 外层固定三个数里最小的那个，下标留出两格给内层的 l 与 r
        for i in range(n - 2):
            # 已排序，nums[i] 是三数中最小者；它一旦为正，三数之和必然为正，
            # 后面的 i 只会更大，直接收工
            if nums[i] > 0:
                break
            # 外层去重：与**前一个**相同则跳过。写成与后一个比会误杀 [0,0,0]，
            # 因为重复值本身可以出现在同一个三元组里，不允许的只是重复输出
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            # 内层在有序区间 [i+1, n-1] 上找和为 -nums[i] 的一对数
            target = -nums[i]
            left = i + 1
            right = n - 1
            while left < right:
                s = nums[left] + nums[right]
                if s < target:
                    left += 1           # 和偏小，只有右移 l 才可能变大
                elif s > target:
                    right -= 1          # 和偏大，只有左移 r 才可能变小
                else:
                    ans.append([nums[i], nums[left], nums[right]])
                    # 命中后把两端与刚用过的值相同的位置整段跳过，
                    # 否则同一个三元组会被重复产出。带 left < 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 ans

LC15 三数之和¶