---
description: "排序后固定一个数、剩下跑有序两数之和；去重靠「同值只当一次代表」，不靠 set"
---

# 15. 三数之和

LeetCode 15[^leetcode] · 中等 · 双指针

## 题

给一个整数数组，找出所有和为 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. 盛最多水的容器](0011-container-with-most-water.md) 一样，每步都安全地丢掉一整行候选。外层再套一层，总共 $O(n^2)$。

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

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

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

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

## 解

```python
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. 两数之和](0001-two-sum.md)。无序、要下标 → 哈希；有序、要值 → 双指针。这题要按值去重，所以排序 + 双指针更顺。
- 四数之和（LeetCode 18[^leetcode-2]）再套一层，$O(n^3)$；外两层都要做同样的跳重。
- 坑：内层找到解后**两个指针都要动**，只动一个会死循环或重复；跳重的比较对象是刚用过的那个值（`l - 1`、`r + 1`）。

??? note "自测"

    ```python
    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]: [LeetCode 15](https://leetcode.cn/problems/3sum/)，2026-09-29 读。
[^leetcode-2]: [LeetCode 18](https://leetcode.cn/problems/4sum/)，2026-09-29 读。