使用 JavaScript 解答 LeetCode 第 1/15/18 题，两数之和、三数之和、四数之和。
N 数之和问题的解题思路是一脉相承的，从最基础的两数之和开始，逐步解决更复杂的计算。
两数之和
原题链接
本题是 LeetCode 题库第 1 题，由此访问。
题目描述
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解题思路
两数之和问题有多种解题方法，暴力法是其中最简单的。暴力法的基本思路是，两次遍历数组，将两次遍历过程中取得的数字依次相加，如结果等于 target 值，返回两数对应下标。暴力法时间复杂度为 O(n^2)，最差情况下需要两次完整的遍历才能取得结果。
我们需要对这一问题尽可能简化，使用哈希表对遍历结果进行存储，可以将两次遍历改为只需一次，时间复杂度控制在 O(n) 水平。根据题目描述，两数之和等于 target，那么在遍历过程中已经指定了其中一个数的下标（设为 n），另一个数则表示为 target-nums[n]。在哈希表中 target-n 键的值设为当前遍历值的下标，当遍历到后续的数字时，查询哈希表即可了解对应数的下标位置。将两个下标位置存储在数组内返回，即是最终答案。
AC 样例
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
const hash = {};
for(let x = 0; x < nums.length; x++) {
if(hash[nums[x]] !== undefined) return [hash[nums[x]], x];
else hash[target-nums[x]] = x;
}
};
三数之和
原题链接
本题是 LeetCode 题库第 15 题，由此访问。
题目描述
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a、b、c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
解题思路
三数之和可以理解为是两数之和的复杂版本，暴力法的时间复杂度达到了 O(n^3)。参考题目描述，数字 a、b、c 之间存在 a+b+c=0 的关系，可以简化为 b+c=-a。按照这一思路，可以将三重遍历简化为一次遍历+一次两数之和计算。
首先对数组进行升序排序。其次遍历数组，设为数字 a，在剩下的范围内求取 b 和 c，判断其是否符合 b+c=-a 的关系。选取 b、c 的过程中为提高效率，使用双指针，分别从数组内 a 之后的范围起止点开始，依次枚举两端数据进行比较。若两数之和大于 -a，则 c 端数字过大，向左移动后再判断；若两数之和小于 -a，则 b 端数字过小，向右移动后再判断；若两数之和等于 -a，则符合题目要求，以数组形式存储于最终结果数组。
当所有数字 a，及其 b、c 遍历完成后，将最终结果二维数组返回。
升序排序使用快速排序算法，时间复杂度为 O(nlogn)；求取 b、c 过程中采用双指针方法，另根据题目要求避免重复数据产生，每次求取 b、c 的最大搜索次数小于数组规模，这一过程时间复杂度为 O(n)；对数字 a 采用一次遍历方法，时间复杂度为 O(n)。综上所述，本算法时间复杂度控制在 O(n^2)。
AC 样例
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
const res = [];
// 数组排序
nums = nums.sort((a, b) => a - b);
// 遍历 a
for(let x = 0; x < nums.length; x++) {
// 重复 a 的排除
if (x > 0 && nums[x] == nums[x-1]) continue;
// 设 c 在 nums 最尾端
let z = nums.length - 1;
const target = -nums[x];
for(let y = x + 1; y < nums.length; y++) {
// 重复 b 的排除
if(y > x + 1 && nums[y] == nums[y-1]) continue;
// 保持 c 始终大于 b
while(z > y && nums[z] + nums[y] > target) z--;
// c b 一致时中止
if (z == y) break;
if(nums[y] + nums[z] == target) res.push([nums[x], nums[y], nums[z]]);
}
}
return res;
};
四数之和
原题链接
本题是 LeetCode 题库第 18 题，由此访问。
题目描述
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c，d，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
解题思路
四数之和问题和三数之和类似，在暴力法情况下时间复杂度可达 O(n^4)，这里我们将其简化，可得数字关系为 (c+d)=target-(a+b)，即将四个数的匹配过程改为两次遍历+一次两数之和计算，整体时间复杂度可控制在 O(n^3) 水平。
首先对数组进行升序排序，之后遍历 a、b，在遍历过程中需要注意去重。在一次循环中，数字 a、b 确定的情况下，求取符合条件的数字 c、d。基本思路与三数之和一致。
对数组排序使用快速排序算法，时间复杂度 O(nlogn)；针对数字 a、b 的遍历，是两次循环，时间复杂度为 O(n^2)；求取数字 c、d 过程中使用双指针，并且为满足不产生重复数据的要求，每次搜索次数小于数组规模，故时间复杂度为 O(n)。综上所述，本算法时间复杂度为 O(n^3)。
AC 样例
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function(nums, target) {
const res = [];
nums = nums.sort((a, b) => a - b);
for(let a = 0; a < nums.length; a++) {
// 去重 a
if(a > 0 && nums[a] == nums[a-1]) continue;
for(let b = a + 1; b < nums.length; b++) {
// 去重 b
if(b > a + 1 && nums[b] == nums[b-1]) continue;
let d = nums.length - 1;
for(let c = b + 1; c < nums.length; c++) {
// 去重 c
if(c > b + 1 && nums[c] == nums[c-1]) continue;
while(d > c && nums[a] + nums[b] + nums[c] + nums[d] > target) d--;
if(d == c) break;
if(nums[a] + nums[b] + nums[c] + nums[d] == target) res.push([nums[a], nums[b], nums[c], nums[d]]);
}
}
}
return res;
};