18. 四数之和（4Sum）
频次 ★★★ · 难度 🟡 · 高频：字节/美团
题目
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a、b、c、d，使得 a + b + c + d = target，找出所有满足条件且不重复的四元组。
示例：
输入: nums = [1, 0, -1, 0, -2, 2], target = 0
输出: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
思路
在三数之和的基础上再加一层循环：排序 + 双重循环固定前两个数 + 双指针找后两个数。
具体：先排序，第一层循环固定 i，第二层循环固定 j（j = i + 1），然后在 (j+1, n-1) 区间内用左右双指针 left 和 right 找两数之和等于 target - nums[i] - nums[j]。每层循环都需要去重（跳过与前一个相同的元素）。
关键细节：四数之和可能超过 int 范围，需要用 long 类型计算和比较。
代码
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;
if (n < 4) {
return result;
}
Arrays.sort(nums);
for (int i = 0; i < n - 3; i++) {
// 去重：跳过与上一个相同的 nums[i]
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 剪枝：最小的四个数之和 > target，后面更大，不可能有解
if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
break;
}
// 剪枝：当前 i 与最大的三个数之和 < target，i 需要增大
if ((long) nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) {
continue;
}
for (int j = i + 1; j < n - 2; j++) {
// 去重：跳过与上一个相同的 nums[j]
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
// 剪枝：当前 i、j 与最小的两个数之和 > target
if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
break;
}
// 剪枝：当前 i、j 与最大的两个数之和 < target
if ((long) nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) {
continue;
}
int left = j + 1, right = n - 1;
while (left < right) {
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
// 去重：跳过重复的 left 和 right
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return result;
}复杂度
- 时间：O(n³) — 排序 O(n log n)，双重循环 O(n²)，内层双指针 O(n)，总体 O(n³)
- 空间：O(log n) — 排序的递归栈空间（不计结果列表）
边界条件
- 数组长度 < 4：直接返回空列表
- 四数之和溢出 int：必须用
long计算和，例如nums = [1000000000, 1000000000, 1000000000, 1000000000]，和超过 int 最大值 - 目标值包含负数：去重和剪枝逻辑不受影响，正常处理
变式
- N 数和通用模板：递归 + 双指针，将 N 数之和转化为 (N-1) 数之和，直到 N=2 时用双指针
- 不排序用哈希表：类似两数之和，用 HashMap 存两两之和，但去重较复杂，且时间复杂度 O(n²) 但常数大
易错点
- 去重位置：每层循环（i、j、left、right）都要去重，漏掉任何一层都会导致结果包含重复四元组
- 剪枝条件不可用
break和continue混淆——break是当前层之后都不可能，continue是当前值不行但后面可能行 - 用
long计算和，不要等溢出后再转——(long) (a + b + c + d)会在括号内先溢出再转
面试追问
- 为什么不用 HashMap 存两两之和？ 可以去重麻烦，且需要额外判断四个下标是否互不相同；双指针法天然有序 + 去重简单，是面试首选。
- 五数之和、六数之和怎么扩展？ 递归降维——K 数之和固定第一个数后递归求 (K-1) 数之和，基准情况 K=2 时用双指针。时间复杂度 O(n