三数之和
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
速度
题目描述
给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0；nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0。不重复三元组是 [-1,0,1] 和 [-1,-1,2]。
示例 2
输入：nums = [0,1,1]
输出：[]
唯一可能的三元组和不为 0。
示例 3
输入：nums = [0,0,0]
输出：[[0,0,0]]
模拟答题者思考
1. 我先写暴力：三重循环枚举 (i,j,k)，判断和是否为 0，O(n³)，还要额外去重。
2. 重复在哪里？固定一个数后，「在剩余数组里找两数之和为 -nums[i]」是经典子问题。
3. 排序后，两数之和可以用双指针：和小了 l++，和大了 r--，O(n)。
4. 外层固定 i，内层双指针找 complement = -nums[i]，整体 O(n²)。
5. 去重关键：排序后，i、l、r 三个位置都要跳过与前一个相同的值，否则会输出重复三元组。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
i | int | 定义：固定三元组中第一个数的位置（排序后最小值） 维护：每轮 i 向右移动，跳过与前一个相同的 nums[i] 更新：for i in range(n-2)，若 nums[i]==nums[i-1] 则 continue |
l | int | 定义：在 i 右侧区间内指向较小候选值的左指针 维护：和太小时右移，找到答案后右移跳过重复 更新：初始 l=i+1；sum<0 时 l++；命中后 while nums[l]==nums[l-1] 则 l++ |
r | int | 定义：在 i 右侧区间内指向较大候选值的右指针 维护：和太大时左移，找到答案后左移跳过重复 更新：初始 r=n-1；sum>0 时 r--；命中后 while nums[r]==nums[r+1] 则 r-- |
ans | list<list> | 定义：所有不重复的三元组答案 维护：每当 nums[i]+nums[l]+nums[r]==0 时追加 [nums[i],nums[l],nums[r]] 更新：命中后 l、r 同时内缩并各自跳过重复值 |
落码步骤
1. 对 nums 升序排序
2. 外层 for i in range(n-2)，若 nums[i]==nums[i-1] 则跳过（i 去重）
3. 设 l=i+1, r=n-1，当 l<r 时计算 s=nums[i]+nums[l]+nums[r]
4. s<0 则 l++；s>0 则 r--；s==0 则记录答案，l、r 内缩并各自跳过重复
5. 返回 ans
代码实现
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
nums.sort()
n = len(nums)
ans = []
for i in range(n - 2):
# 固定第一个数，跳过重复
if i > 0 and nums[i] == nums[i - 1]:
continue
l, r = i + 1, n - 1
while l < r:
s = nums[i] + nums[l] + nums[r]
if s < 0:
l += 1
elif s > 0:
r -= 1
else:
ans.append([nums[i], nums[l], nums[r]])
l += 1
r -= 1
# 跳过 l、r 侧的重复值
while l < r and nums[l] == nums[l - 1]:
l += 1
while l < r and nums[r] == nums[r + 1]:
r -= 1
return ansclass Solution {
public:
vector> threeSum(vector& nums) {
sort(nums.begin(), nums.end());
int n = nums.size();
vector> ans;
for (int i = 0; i < n - 2; i++) {
// 固定第一个数，跳过重复
if (i > 0 && nums[i] == nums[i - 1]) continue;
int l = i + 1, r = n - 1;
while (l < r) {
int s = nums[i] + nums[l] + nums[r];
if (s < 0) l++;
else if (s > 0) r--;
else {
ans.push_back({nums[i], nums[l], nums[r]});
l++; r--;
// 跳过 l、r 侧的重复值
while (l < r && nums[l] == nums[l - 1]) l++;
while (l < r && nums[r] == nums[r + 1]) r--;
}
}
}
return ans;
}
};
// 时间 O(n²)，空间 O(1)（不计排序） 复杂度分析
时间复杂度
O(n²)
空间复杂度
O(1)（不计排序）
常见坑
忘记排序：不排序就无法用双指针单调移动，也无法方便地去重。
只在一处去重：i、l、r 三个位置都可能产生重复三元组，三处都要跳过相同值。
命中后忘记移动指针：找到一组答案后必须 l++、r--，否则会死循环在同一组 (l,r) 上。
必测边界 Case
Case 1：全零
nums = [0,0,0] → [[0,0,0]]
Case 2：不足三个元素
nums = [1,2] → []
Case 3：大量重复值
nums = [-1,-1,0,1,1] → [[-1,0,1]]（只输出一组）