15. 三数之和 (Medium)

专题归类： 02-双指针与滑动窗口 · 01-哈希表 LeetCode 链接： https://leetcode.cn/problems/3sum/

---

在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode

题目描述

给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。

请你返回所有和为 0 且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

示例：

输入：nums = [-1, 0, 1, 2, -1, -4]
输出：[[-1, -1, 2], [-1, 0, 1]]
解释：注意 [-1, 0, 1] 和 [0, 1, -1] 被视为重复

补充说明：

• 数组长度范围：3 <= nums.length <= 3000
• 数值范围：-10^5 <= nums[i] <= 10^5

---

题目详细分析

数据范围含义：

• 长度最大 3000，O(n^2) 是可行的（约 9×10^6 次操作），但 O(n^3) 则完全不可行（2.7×10^10 次操作）。
• 数值范围 ±10^5，三数之和最大可达 ±3×10^5，在 32 位整数范围内。

核心约束：

• 去重是本题最难的部分，而不是找到三元组本身。题目要求”不重复的三元组”，意味着 [-1, 0, 1] 和 [0, -1, 1] 被视为重复。
• 三个下标互不相同，但值可以相同（如 [-1, -1, 2] 中的两个 -1 是不同的元素）。

边界条件：

• 数组长度小于 3：直接返回空列表。
• 全为 0：只有一个三元组 [0, 0, 0]，不要重复返回。
• 没有符合条件的三元组：返回空列表。

隐藏条件：

• 排序可以大大简化去重。排序后，相同的元素会相邻，我们可以方便地跳过重复元素。
• 排序后可以剪枝：如果 nums[i] > 0，后面的数都比它大，三数之和不可能为 0。
• 去重需要在三个层面进行：固定元素 i、左指针 left、右指针 right。

---

小白版直白理解

想象你要从一堆数字卡片中找出三张，让它们加起来等于 0。

笨办法： 把所有三张卡片的组合都试一遍。n 张卡片有大约 n³/6 种组合，太多了。

聪明办法： 先把卡片按数字从小到大排好（排序）。然后拿出一张卡片固定住（比如 -1），问题就变成了”在剩下的卡片中找两张，加起来等于 1”——这就是一道两数之和问题！而找两数之和，你从剩余卡片的两端开始，用两个指针往中间靠（因为已经排好序了）。

去重技巧： 排序后，重复的数字会挨在一起。你只需要记住规则：

1. 固定卡片时，如果和上一张一样，跳过它。
2. 找到一组后，移动指针时如果遇到相同的数字，继续跳过。

这样就确保不会找到重复的三元组。

---

解题思路

思路一：排序 + 对撞指针（推荐）

核心想法： 排序后，固定一个数 nums[i]，在 [i+1, n-1] 区间内用对撞指针找两数之和为 -nums[i]。

关键洞察： 排序带来了三个好处：

1. 双指针可以 O(n) 找两数之和（有序数组两数之和的标准解法）。
2. 去重变得简单——相邻重复元素可以直接跳过。
3. 可以剪枝——nums[i] > 0 时直接结束。

去重策略（三个层面）：

• 外层 i：如果 nums[i] == nums[i-1]，跳过（避免同一值当固定元素多次）。
• 内层 left：找到答案后，跳过 nums[left] == nums[left-1]。
• 内层 right：找到答案后，跳过 nums[right] == nums[right+1]。

def threeSum(nums):
    """
    排序 + 对撞指针
    
    步骤：
    1. 排序
    2. 固定 i，在 [i+1, n-1] 内用双指针找两数之和为 -nums[i]
    3. 三层去重：i 去重、left 去重、right 去重
    """
    nums.sort()
    n = len(nums)
    res = []
    
    for i in range(n - 2):
        # 剪枝：最小的数 > 0，和不可能为 0
        if nums[i] > 0:
            break
        
        # 外层去重：跳过重复的固定元素
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        left, right = i + 1, n - 1
        target = -nums[i]
        
        while left < right:
            s = nums[left] + nums[right]
            if s < target:
                left += 1
            elif s > target:
                right -= 1
            else:
                # 找到一组解
                res.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                
                # 内层去重：跳过重复元素
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
    
    return res

思路二：哈希表法

核心想法： 固定两个数，用哈希表查找第三个数。

但实际上，这道题用哈希表不如双指针优雅，因为：

1. 哈希表法去重更麻烦。
2. 哈希表法需要 O(n) 额外空间。
3. 时间复杂度同样是 O(n

def threeSum_hash(nums):
    """哈希表法，去重较麻烦"""
    nums.sort()
    n = len(nums)
    res = []
    
    for i in range(n - 2):
        if nums[i] > 0:
            break
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        seen = set()
        for j in range(i + 1, n):
            complement = -(nums[i] + nums[j])
            if complement in seen:
                res.append([nums[i], complement, nums[j]])
                # 去重
                while j + 1 < n and nums[j + 1] == nums[j]:
                    j += 1
            seen.add(nums[j])
    
    return res

---

易错点

• 去重时机： 外层去重要在进入循环时判断（if i > 0 and nums[i] == nums[i-1]: continue），而不是找到答案后再去重。内层去重要在找到答案后进行。
• 去重遗漏： 如果只在外层去重，内层可能产生重复。比如 nums = [-2, 0, 0, 2, 2]，固定 -2 后，left=0, right=2 得到 [-2, 0, 2]，left=0, right=2（另一个 2）又会得到同样的 [-2, 0, 2]。所以内层也要去重。
• 剪枝条件： 是 nums[i] > 0 而不是 nums[i] >= 0。因为 nums[i] 可以为 0（如 [0, 0, 0]）。如果写 >=，会漏掉全 0 的情况。
• 指针初始化： left = i + 1，不是 left = 0。如果 left 从 0 开始，可能会和 nums[i] 重复使用同一个元素。
• 边界检查： 内层去重的 while 循环需要判断 left < right，防止越界。
• 别忘了先排序： 如果忘记了排序步骤，双指针无法正常工作（无序数组的双指针无法保证正确性）。

---

框架提炼

排序 + 对撞指针查找模板（N 数之和）：

将 N 数之和问题转化为 (N-1) 数之和问题，直到变为两数之和用对撞指针解决。

def nSum(nums, target, n):
    """
    通用 N 数之和模板（递归版）
    """
    nums.sort()
    
    def n_sum(start, target, n):
        res = []
        if n == 2:
            # 两数之和：对撞指针
            left, right = start, len(nums) - 1
            while left < right:
                s = nums[left] + nums[right]
                if s < target:
                    left += 1
                elif s > target:
                    right -= 1
                else:
                    res.append([nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1
            return res
        else:
            # 递归：固定一个数，求 (n-1) 数之和
            for i in range(start, len(nums) - n + 1):
                if nums[i] > target / n:  # 剪枝优化
                    break
                if i > start and nums[i] == nums[i - 1]:
                    continue  # 去重
                sub_res = n_sum(i + 1, target - nums[i], n - 1)
                for sub in sub_res:
                    res.append([nums[i]] + sub)
            return res
    
    return n_sum(0, target, n)

---

关联题目

• 1-两数之和 — 两数之和是本题的基础版本。三数之和本质上是”固定一个数 + 两数之和”。但两数之和用哈希表，三数之和用排序 + 双指针（因为需要去重）
• 16-最接近的三数之和 — 本题的变体，找和最接近 target 的三元组。同样用排序 + 双指针，但不需要严格等于，而是维护最小差值
• 18-四数之和 — 本题的扩展，四数之和 = 固定一个数 + 三数之和，可以用递归模板统一处理