0018.四数之和
难度：🟡 中等
标签：数组、双指针、排序
链接：18. 四数之和
题目描述
给你一个由 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：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
解题思路
核心思想
本题是“三数之和”问题的自然延伸。核心思想是通过固定两个数，将“四数之和”问题降维成一个“两数之和”的问题。为了高效地解决子问题并处理重复解，排序是必不可少的第一步。
思路选择
排序 + 双指针 是解决此类问题的通用且高效的思路。
我们首先对数组进行排序。
使用两层嵌套的
for循环来固定前两个数nums[i]和nums[j]。对于固定的
i和j，问题就变成了在数组的剩余部分[j+1, n-1]中，寻找两个数，使它们的和等于target - nums[i] - nums[j]。这个“两数之和”的子问题，可以利用数组的有序性，通过左右两个指针
left和right在 O(n) 的时间内解决。整个算法的关键在于，在每一层（固定
i，固定j，以及双指针移动时）都要进行剪枝和去重操作，以避免不必要的计算和产生重复的四元组。
关键步骤
排序：首先对整个数组
nums进行升序排序。第一层循环（固定
i）： a. 进行剪枝：如果当前nums[i]加上后面最小的三个数都大于target，或者nums[i]加上后面最大的三个数都小于target，则可以进行剪枝。 b. 去重：如果nums[i]与前一个数nums[i-1]相同，跳过。第二层循环（固定
j）： a. 进行类似的剪枝操作。 b. 去重：如果nums[j]与前一个数nums[j-1]相同，跳过。双指针查找（
left和right）： a. 初始化left = j + 1,right = nums.length - 1。 b. 在left < right的条件下循环，计算四数之和sum。 c. 根据sum与target的大小关系移动left或right指针。 d. 如果sum === target，则找到了一个解。将其存入结果集，并对left和right指针进行去重处理，然后同时移动它们。返回结果：遍历结束后，返回包含所有不重复四元组的结果集。
代码实现
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function (nums, target) {
let results = [];
nums.sort((a, b) => a - b);
for (let i = 0; i < nums.length; i++) {
// 第一个数的去重
if (i > 0 && nums[i] === nums[i - 1]) continue;
for (let j = i + 1; j < nums.length; j++) {
// 第二个数的去重
if (j > i + 1 && nums[j] === nums[j - 1]) continue;
let left = j + 1, right = nums.length - 1;
while (left < right) {
let total = nums[i] + nums[j] + nums[left] + nums[right];
if (total === target) {
results.push([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 (total < target) left++;
else right--;
}
}
}
return results;
};
复杂度分析
时间复杂度：O(n³) 数组排序的时间复杂度为 O(n log n)。两层
for循环和一层while循环构成了 O(n³) 的复杂度。总体上，O(n³) 占主导地位。空间复杂度：O(log n) 或 O(n) 不考虑存储结果的数组，空间复杂度主要取决于排序算法所需的栈空间。
相关题目
总结
本题是“N数之和”系列问题中的一个典型。其通用的解题范式是“排序 + 递归/多层循环 + 双指针”，通过降维的方式将复杂问题简化。解题的关键和难点在于处理好多层嵌套下的剪枝和去重逻辑，以确保解的正确性和唯一性。