LeetCode 18. 四数之和
题目描述
✅ 18. 四数之和
题意分析
从数组中选出四个不同下标，使四个数的和等于
target，返回所有不重复的四元组。不同位置可以存放相同数值，但一个位置不能被重复使用。答案按数值组合去重：用不同下标选出了相同的四个数，只能输出一次；同一四元组内部换顺序也不算新答案。因此既要保留输入中重复值可被多次选用的能力，又要避免重复输出。
解法：排序 + 双层固定 + 双指针
核心思路
[!blue]
先把数组升序排序。固定前两个位置
i、j后，问题就变成在它们右侧寻找两数，使四数和达到目标。令left = j + 1、right = n - 1，始终保持i < j < left < right，四个下标自然互不相同。若当前和偏小，固定当前
left再减小right只会让和更小，因此这个left已不可能组成答案，可以右移它。若当前和偏大，固定当前right再增大left只会让和更大，因此可以左移right。每次移动都排除了一批确定无解的配对，不会漏掉目标和。和相等时记录四元组，然后同时移动两端并跳过刚用过的重复值。对于固定的前两个数，一个左值对应的目标右值已经确定，再用相同左值或相同右值只能得到同样的数值组合。
外层也要按层去重：相同的第一个数只处理一次；固定
i后，相同的第二个数也只处理一次。但j == i + 1是当前层的第一个候选，即使它与nums[i]相同也不能跳过。去重的是同一位置角色上的重复选择，不能先把整个数组中的相同值删掉。排序使每个四元组都有唯一的非递减表示，按层去重保证它只被输出一次。四个数相加可能超出 32 位范围，因此必须在开始加法前提升到 64 位，不能先用窄整数求和后再转换。
解题步骤
- 将数组升序排序，枚举能给后面留下至少三个位置的
i，跳过与上一轮相同的第一个值。- 对每个
i，从i + 1开始枚举j；仅在j > i + 1时跳过与前一个相同的第二个值。- 在
j右侧初始化双指针，用 64 位计算四数和。- 和偏小就右移
left，偏大就左移right；相等则保存答案，同时收缩两端并跳过重复值。- 两指针相遇后结束本轮，完成所有固定位置后返回答案列表。
代码实现
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
int n = nums.length;
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 left = j + 1;
int right = n - 1;
while (left < right) {
// 使用 long 计算四数和，避免极值输入溢出。
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
res.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--;
}
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return res;
}
}
import "sort"
func fourSum(nums []int, target int) [][]int {
sort.Ints(nums)
res := make([][]int, 0)
n := len(nums)
for i := 0; i < n-3; i++ {
if i > 0 && nums[i] == nums[i-1] {
continue
}
for j := i + 1; j < n-2; j++ {
// 第二层只在当前起点之后去重，不能误跳过本轮第一个候选。
if j > i+1 && nums[j] == nums[j-1] {
continue
}
left := j + 1
right := n - 1
for left < right {
// 先将每个加数提升到宽整数，再计算四数和。
sum := int64(nums[i]) + int64(nums[j]) + int64(nums[left]) + int64(nums[right])
if sum == int64(target) {
res = append(res, []int{
nums[i],
nums[j],
nums[left],
nums[right],
})
left++
right--
for left < right && nums[left] == nums[left-1] {
left++
}
for left < right && nums[right] == nums[right+1] {
right--
}
} else if sum < int64(target) {
left++
} else {
right--
}
}
}
}
return res
}
复杂度分析
设数组长度为 $n$，答案数量为 $r$。
- 时间复杂度：$O(n^3)$。排序为 $O(n\log n)$，两层固定位置枚举为 $O(n^2)$，每次双指针最多线性移动。
- 辅助空间复杂度：双指针与枚举变量占 $O(1)$，计入当前排序实现的调用栈通常为 $O(\log n)$；返回结果另占 $O(r)$。
关键点总结
[!green]
- 排序提供双指针移动的单调性，也让相同数值的候选相邻。
- 四个下标严格递增，去重按当前层进行，不删除重复元素本身。
- 先扩展数值类型再求和，保证比较结果和移动方向正确。
易错点总结
[!yellow]
- 四数先按 32 位相加再转成 64 位，溢出已经发生，必须在加法前提升类型。
- 第二层去重漏掉
j > i + 1，会把当前层第一次允许使用的重复值也跳过。- 命中后不移动两端或不跳过重复值，会重复处理相同组合，甚至无法推进。
- 使用
left <= right会在指针重合时重复使用同一下标，应保持严格小于。- 输入未排序时不能套用双指针移动规则；也不能通过全局去重来代替答案去重。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 15. 三数之和 | 中等 | 从三数之和扩展为固定两项，剩余两项用双指针并处理重复组合。 |
| 454. 四数相加 II | 中等 | 同样把四项拆成两两组合，原题四个独立数组可用两数和频次表，本题还需防止同一下标复用。 |
| 16. 最接近的三数之和 | 中等 | 排序后固定部分元素，再用左右指针收缩候选；本题多固定一个数寻找四元组，该题根据与目标的距离更新最接近的和。 |
| 259. 较小的三数之和 | 中等 | 排序后固定部分元素，再用左右指针收缩候选；本题多固定一个数寻找四元组，该题满足阈值时批量累计指针对数。 |
| 611. 有效三角形的个数 | 中等 | 排序后固定部分元素，再用左右指针收缩候选；本题多固定一个数寻找四元组，该题把三角不等式转为两数和比较。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！