四数之和
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
给你一个由 n 个整数组成的数组 nums，和一个目标值 target。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c和d互不相同nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案。
示例 1
示例 2
模拟答题者思考
1. 我先写暴力：四重循环枚举 (i,j,l,r)，判断四数之和是否等于 target——O(n⁴)，还要额外去重，肯定超时。
2. 重复在哪里？固定前两个数 nums[i]、nums[j] 后，问题变成「在剩余数组里找两数，使四数之和等于 target」，即两数之和 = target - nums[i] - nums[j]。
3. 这和 #15 三数之和一脉相承：排序后，两数之和可用双指针——和小了 l++，和大了 r--，O(n)。
4. 整体结构：排序 → 外层固定 i → 中层固定 j → 内层双指针找 complement，复杂度 O(n³)。
5. 去重关键：排序后 i、j、l、r 四个位置都要跳过与前一个相同的值；另外 C++ 里求和要用 long long 防溢出。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
i | int | 定义：四元组中第一个固定数在排序数组中的下标（最小候选） 维护：外层枚举，每轮锁定 nums[i] 后在内层继续找 (j,l,r)更新： for i in range(n-3)；若 nums[i]==nums[i-1] 则 continue 去重 |
j | int | 定义：四元组中第二个固定数在 i 右侧的下标维护：在 (i, n-2] 区间枚举，与 i 一起把问题降为「两数之和 = target-nums[i]-nums[j]」更新： for j in range(i+1, n-2)；若 j>i+1 且 nums[j]==nums[j-1] 则 continue 去重 |
l | int | 定义：在 j 右侧区间内指向较小候选值的左指针维护：当前四数和偏小则右移，命中后跳过重复值 更新：初始 l=j+1；s<target 时 l++；命中后 while 跳过相同 nums[l] |
r | int | 定义：在 j 右侧区间内指向较大候选值的右指针维护：当前四数和偏大则左移，命中后跳过重复值 更新：初始 r=n-1；s>target 时 r--；命中后 while 跳过相同 nums[r] |
ans | list<list> | 定义：所有不重复的四元组答案 维护：每当 nums[i]+nums[j]+nums[l]+nums[r]==target 时追加一组更新：命中后 l、r 同时内缩并各自跳过重复，避免死循环与重复答案 |
落码步骤
1. 对 nums 升序排序；若 n<4 直接返回空列表
2. 外层 for i in range(n-3)，若 nums[i]==nums[i-1] 则跳过（i 去重）
3. 中层 for j in range(i+1, n-2)，若 nums[j]==nums[j-1] 且 j>i+1 则跳过（j 去重）
4. 设 l=j+1, r=n-1，当 l<r 时计算 s=nums[i]+nums[j]+nums[l]+nums[r]
5. s<target 则 l++；s>target 则 r--；s==target 则记录答案，l、r 内缩并各自跳过重复
6. 返回 ans
代码实现
class Solution:
def fourSum(self, nums: list[int], target: int) -> list[list[int]]:
nums.sort()
n = len(nums)
ans = []
for i in range(n - 3):
# 固定第一个数，跳过重复
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, n - 2):
# 固定第二个数，跳过重复
if j > i + 1 and nums[j] == nums[j - 1]:
continue
l, r = j + 1, n - 1
while l < r:
s = nums[i] + nums[j] + nums[l] + nums[r]
if s < target:
l += 1
elif s > target:
r -= 1
else:
ans.append([nums[i], nums[j], 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 ansclass Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int n = nums.size();
vector<vector<int>> ans;
long long t = target;
for (int i = 0; i < n - 3; i++) {
// 固定第一个数，跳过重复
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < n - 2; j++) {
// 固定第二个数，跳过重复
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int l = j + 1, r = n - 1;
while (l < r) {
long long s = (long long)nums[i] + nums[j] + nums[l] + nums[r];
if (s < t) l++;
else if (s > t) r--;
else {
ans.push_back({nums[i], nums[j], nums[l], nums[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 去重、忘记 j 去重：第二个固定数相同会产出重复四元组，j 处也要 continue。
C++ 用 int 直接相加：四个数各可达 10⁹，和会溢出，求和应转 long long。
命中后忘记移动 l、r：找到一组答案后必须双指针内缩并跳过重复，否则会死循环或重复收集。
必测边界 Case
nums = [1,2], target = 3 → []
nums = [2,2,2,2], target = 8 → [[2,2,2,2]]
nums = [1,0,-1,0,-2,2], target = 0 → 三组不重复四元组（见示例 1）