题目链接：18. 四数之和
这个人已经靠 n 数之和水了好几篇文章了，已经不想再水了
我之前写过好几篇的 nSum 相关的文章，在我的个人主页里面搜索可以发现有三篇相关的文章
当然看的人不多，但是还是决定要把这个类型题写完，也就是今天的终章 nSum，在这也引下流，也方便搜索往前的知识
上面的文章中最关键的就是leetcode_15. 三数之和这篇文章
一、题目描述：
给你一个由 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]]提示：
1 <= nums.length <= 200-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9
题目模板
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function (nums, target) {};二、思路分析：
我在leetcode_15. 三数之和这篇文章说过（没有看过的去看一下），如何把 n 降级成我们容易理解的 2 数之和，最重要的就是移位，变更我们的 target 值，这道四数之和要求解的公式为
四数之和
a + b + c + d = target
三数之和
a + b + c = 0其实和三数之和没有区别，不就是 target 变成了 0 而已，并没有什么实质性的变化，所以四数之和的思路同样是去变换 target 值然后去寻找合适的数，用下面的图来理解一下
发现了吗？无论是几数之和，都是在两数之和的基础上再加上一层 for 循环，两数之和就是我们的 base case，我们要做到就是一层层的嵌套循环，反过来就是一个递归，每一次往下递归我们都将把 n 的层数减一，最终到我们的 base case 两数之和，所以 nSum 的答案已经出来了，就是下面的伪代码
const nSum = (nums, n, start, target) => {
if (n === 2) {
返回两数之和的结果;
} else {
for (let i = start; i < length - 2; i++) {
得到 n - 1 数之和的结果
res.push(nSum(nums, n - 1, i + 1, target - nums[i]));
}
}
return res;
};nSum 最终的代码就可以用一个简单的递归完成了
边界处理
整体的框架没变，但是还要处理一些细节，就拿题目的示例来说 nums = [2,2,2,2,2], target = 8，可能的答案有下面这些
它们只是索引不同，但是数值是一致的，按照题目的要求，
不重复的四元组 [nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）
我们给出上面的答案是不满足题目的要求的，但也还是有解决方法的，解决方法很简单，就是跳过重复的元素，重复的元素进入到循环后会执行同样的操作，
a + b + c + d = target
若 a = 2, 其后紧跟的元素也为 2，则递归相同
b + c + d = target - 2,
c + d = target - 2 - b但是题目所给的 nums 是无序的，因此我们需要将数组进行排序，让 nums 中重复的元素能够彼此相邻
综上，最终 AC 代码如下
三、AC 代码：
var fourSum = function (nums, target) {
const twoSum = (nums, start, target) => {};
const nSum = (nums, n, start, target) => {
const result = [];
if (nums.length < n || n < 2) {
return result;
}
if (n === 2) {
result.push(...twoSum(nums, start, target));
} else {
const length = nums.length;
// 当数组剩余数量小于 n 时退出
for (let i = start; i <= length - n; i++) {
const tempRes = nSum(nums, n - 1, i + 1, target - nums[i]);
for (const res of tempRes) {
result.push([nums[i], ...res]);
}
while (i <= length - n && nums[i] === nums[i + 1]) i++;
}
}
return result;
};
nums.sort((a, b) => a - b);
return nSum(nums, 4, 0, target);
};AC 代码的时间复杂度，有下面几个部分
- 排序时间复杂度 -
JS sort用的是快排，时间复杂度为O(nlogn) - 递归时间复杂度 -
n^3，n = 4, n = 3遍历可能的结果需要时间复杂度为O(n)，而两数之和的时间复杂度为O(n)（这里我采用的是两数之和的双指针解法）
所以总的时间复杂度为 O(n^3)
总结
四数之和，五数之和，六数之和都可以使用上面的解法，它们的时间复杂度都是再套一个 for 循环，即 O(n)，为 O(n^(k-1))（假设为 K 数之和）
