跳到主要内容

15. 三数之和

题目描述​

给你一个整数数组 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]]
  • 输入：nums = [0,1,1] → 输出：[]
  • 输入：nums = [0,0,0] → 输出：[[0,0,0]]

解题思路​

第一步：理解问题本质​

这道题的核心挑战有两点：

  1. 找出所有满足三数之和为 0 的组合。
  2. 去除重复的三元组。

如果用暴力枚举，去重是最麻烦的部分。而排序是解决去重问题的利器——排序后，相同的数字紧挨在一起，跳过重复元素只需要一个简单的判断。

第二步：暴力解法​

三层嵌套循环，枚举所有三元组，用集合去重。

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        result = set()
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if nums[i] + nums[j] + nums[k] == 0:
                        triple = tuple(sorted([nums[i], nums[j], nums[k]]))
                        result.add(triple)
        return [list(t) for t in result]

时间复杂度：O(n³)，对于 n = 3000 约有 2.7 × 10¹⁰ 次操作，远超时间限制。

为何不够：三层循环枚举了大量无效组合，且用集合去重有额外开销。需要利用"有序"的性质减少枚举量。

第三步：优化解法（排序 + 哈希表）​

固定第一个数 nums[i]，问题转化为在剩余数组中找两数之和等于 -nums[i]（即两数之和问题）。用哈希集合可以将内层两数之和从 O(n²) 降到 O(n)。

整体复杂度降到 O(n²)，但去重逻辑仍然需要用集合，代码不够优雅。

第四步：最优解法（排序 + 双指针）​

排序 + 双指针是这道题的标准最优解。排序后，我们可以用双指针在 O(n) 时间内完成两数之和的搜索，同时天然支持去重跳过。

完整思路：

  1. 排序：将数组从小到大排序，使相同元素相邻，便于去重。
  2. 固定第一个数：用 first 从左到右枚举第一个数 nums[first]。
    • 若 nums[first] > 0，由于数组有序，后面的数只会更大，三数之和不可能为 0，直接 break。
    • 若 nums[first] == nums[first-1]（且 first > 0），跳过，避免重复三元组。
  3. 双指针找剩余两数：在 first+1 到 n-1 范围内，用 second 从左、third 从右向中间夹逼，目标是 nums[second] + nums[third] == -nums[first]（即 target）。
    • 若 nums[second] + nums[third] > target：和太大，third 左移（减小右侧的数）。
    • 若 nums[second] + nums[third] < target：和太小，second 右移（增大左侧的数）。
    • 若相等：记录结果，继续移动 second 右移（同时 third 会在 while 循环中自动跟进）。
    • second 去重：若 nums[second] == nums[second-1]（且 second > first+1），跳过。

为什么双指针有效：数组有序后，second 和 third 的增减方向是确定的——second 只向右移，third 只向左移，两者不会回头，所以整个内层循环是 O(n) 的。

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        if n < 3:
            return []
        nums.sort()
        ans = []
        for first in range(n):
            # 跳过重复的第一个数
            if first > 0 and nums[first] == nums[first - 1]:
                continue
            # 最小的数已大于 0，不可能凑出三数和为 0
            if nums[first] > 0:
                break
            third = n - 1
            target = -nums[first]
            for second in range(first + 1, n):
                # 跳过重复的第二个数
                if second > first + 1 and nums[second] == nums[second - 1]:
                    continue
                # third 左移直到不大于 target
                while second < third and nums[second] + nums[third] > target:
                    third -= 1
                # 两指针相遇，后续 second 增大只会让和更小，无解
                if second == third:
                    break
                if nums[second] + nums[third] == target:
                    ans.append([nums[first], nums[second], nums[third]])
        return ans

完整代码实现​

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        if n < 3:
            return []
        nums.sort()
        ans = []
        for first in range(n):
            if first > 0 and nums[first] == nums[first - 1]:
                continue
            if nums[first] > 0:
                break
            third = n - 1
            target = -nums[first]
            for second in range(first + 1, n):
                if second > first + 1 and nums[second] == nums[second - 1]:
                    continue
                while second < third and nums[second] + nums[third] > target:
                    third -= 1
                if second == third:
                    break
                if nums[second] + nums[third] == target:
                    ans.append([nums[first], nums[second], nums[third]])
        return ans

示例推演​

以 nums = [-1, 0, 1, 2, -1, -4] 为例，期望输出 [[-1,-1,2], [-1,0,1]]。

排序后：[-4, -1, -1, 0, 1, 2]，索引 0~5。

first = 0，nums[first] = -4，target = 4，third = 5：

secondnums[second]nums[third]和操作
1-12（idx=5）11 < 4，second 右移
2-12（idx=5）11 < 4，second 右移
302（idx=5）22 < 4，second 右移
412（idx=5）33 < 4，second 右移
5second == third，break

本轮无结果。

first = 1，nums[first] = -1，target = 1，third = 5：

secondnums[second]third 位置nums[third]和操作
2-1521== target，记录 [-1,-1,2]，second 右移
305（while: -1+2=1 不>1，不移）222 > 1，while: third 左移到 4
411== target，记录 [-1,0,1]，second 右移
414（while: 0+1=1 不>1）12second == third（均为4），break

本轮找到 [-1,-1,2] 和 [-1,0,1]。

first = 2，nums[first] = -1，与 nums[first-1] = -1 重复，跳过。

first = 3，nums[first] = 0 > 0为假，nums[first] = 0，继续；first = 3, nums[3]=0，target = 0，third = 5：

second=4, nums[4]=1, nums[5]=2, 和=3 > 0, third 左移到 4；second==third，break。无结果。

first = 4，nums[first] = 1 > 0，break。

最终结果：[[-1,-1,2], [-1,0,1]]，正确。

复杂度分析​

解法时间复杂度空间复杂度说明
暴力（三重循环）O(n³)O(n)集合去重，超时
排序 + 哈希表O(n²)O(n)内层哈希查找，去重需额外集合
排序 + 双指针O(n²)O(1)内层双指针 O(n)，去重靠跳过相邻重复

排序本身 O(n log n)，被 O(n²) 主导，整体仍为 O(n²)。空间复杂度不计输出结果占用的空间。

易错点总结​

  1. 第二个数的去重时机：second 的去重条件是 second > first + 1，而不是 second > 0。这是因为 second 的起始位置是 first + 1，第一次取值不需要跳过。
  2. third 的初始化位置：third = n - 1 的初始化在 first 的循环内，每次 second 推进时，third 不重置，因为有序数组中 second 增大意味着 target - nums[second] 减小，需要的 third 也只会更小或不变，不需要右移回去。这是双指针高效的关键。
  3. second == third 时立刻 break：此时两指针相遇，后续 second 继续增大只会让两数之和变小，不可能等于 target，所以整个内层循环可以终止。
  4. nums[first] > 0 时 break 而非 continue：数组有序，first 后面的数只会更大，不可能再有三数之和为 0 的情况，应 break 终止外层循环，而非 continue 跳过当前。

扩展思考​

  • 两数之和（LeetCode 1）：本题内层双指针部分本质上就是有序数组的两数之和，理解这个子问题有助于掌握三数之和。
  • 四数之和（LeetCode 18）：再加一层固定第一个数的循环，内层依然是三数之和（双指针），复杂度为 O(n³)。
  • 双指针本质：双指针之所以有效，是因为有序数组中，second 和 third 的移动方向是单调的——second 只向右、third 只向左，两者合计移动步数不超过 n，保证了 O(n) 的内层复杂度。这是"有序"性质带来的核心优化。
加载评论中...