企业官网建设流程全解析

LeetCode 18. 四数之和的核心解法是排序 + 双指针，时间复杂度为 O(n³)，本质是三数之和的扩展：固定前两个数，再用双指针找后两个数。

核心思路
1. 排序：便于使用双指针和去重
2. 两层循环：枚举前两个数 nums[i] 和 nums[j]
3. 双指针：在剩余区间用 left 和 right 找后两个数
4. 去重：每层都要跳过重复元素，避免结果重复

Java 完整实现
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length < 4) return res;

Arrays.sort(nums);
int n = nums.length;

for (int i = 0; i < n - 3; 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;
// 剪枝：当前数 + 最大的三个数仍小于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++) {
// 去重：跳过相同的第二个数
if (j > i + 1 && nums[j] == nums[j - 1]) continue;

// 剪枝：当前最小的四数之和已大于target
if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
// 剪枝：当前两数 + 最大的两个数仍小于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) {
res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[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 res;
}
}

关键细节
- sum 用 long：题目中 nums[i] 范围是 -10⁹ ~ 10⁹，四个数相加可能超出 int 范围，必须用 long 防止溢出
- 去重条件 j > i + 1：第二层去重判断的是 j > i + 1 而非 j > 0，因为 j 的合法起始位置是 i + 1，第一个 j 不应被跳过
- 剪枝不能简单用 nums[i] > target：因为数组中可能有负数，nums[i] > target 不代表后续组合一定超 target，必须用四数之和的上下界来判断
- 去重在找到解之后：left 和 right 的去重只在 sum == target 时执行，确保不遗漏合法组合

复杂度
项目 复杂度
时间 O(n³)
空间 O(log n)（排序栈空间）

这道题的套路和三数之和完全一致，掌握后可以推广到 N 数之和（递归 + 双指针），属于双指针系列的必刷经典题。

要不要顺带看看 N 数之和的通用递归框架？四数之和其实是它的特例，掌握框架后能直接套。