15. 三数之和

LeetCode 15¹ · 中等 · 双指针

题

给一个整数数组，找出所有和为 0 的三元组（三个下标互不相同），结果里不能有重复的三元组（按值去重）。

例：[-1, 0, 1, 2, -1, -4] → [[-1, -1, 2], [-1, 0, 1]]。

一句话

排序；外层枚举最小的那个数 a，内层在它右边用左右指针找和为 -a 的两个数，三处都跳过重复值。

关键技巧

降维：\(k\) 数之和 = 枚举一个 + \((k-1)\) 数之和。 两数之和在有序数组上有 \(O(n)\) 的双指针：s = nums[l] + nums[r]，s 小了 l++，大了 r--——和 11. 盛最多水的容器一样，每步都安全地丢掉一整行候选。外层再套一层，总共 \(O(n^2)\)。

排序同时解决了去重。 值相同的元素排在一起，只要规定「同一个值在同一位置只当一次代表」：

外层：i > 0 and nums[i] == nums[i-1] 跳过——以相同值打头的三元组上一轮已经全部找过；
内层：找到一组后，l 和 r 各自越过所有等值元素再继续。

这样每个值三元组恰好产出一次，不用 set(tuple(...)) 事后去重。

剪枝：nums[i] > 0 直接 break。 最小的数都是正的，后面不可能凑出 0。

解

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

时间 \(O(n^2)\)，空间 \(O(\log n)\)（排序栈，不计输出）。

延伸

起点：1. 两数之和。无序、要下标 → 哈希；有序、要值 → 双指针。这题要按值去重，所以排序 + 双指针更顺。
四数之和（LeetCode 18²）再套一层，\(O(n^3)\)；外两层都要做同样的跳重。
坑：内层找到解后两个指针都要动，只动一个会死循环或重复；跳重的比较对象是刚用过的那个值（l - 1、r + 1）。

自测

s = Solution()
assert sorted(s.threeSum([-1, 0, 1, 2, -1, -4])) == [[-1, -1, 2], [-1, 0, 1]]
assert s.threeSum([0, 1, 1]) == []
assert s.threeSum([0, 0, 0]) == [[0, 0, 0]]
assert s.threeSum([0, 0, 0, 0]) == [[0, 0, 0]]
assert sorted(s.threeSum([-2, 0, 1, 1, 2])) == [[-2, 0, 2], [-2, 1, 1]]

LeetCode 15，2026-09-29 读。 ↩
LeetCode 18，2026-09-29 读。 ↩