n 数之和¶
统计信息：字数 7013 阅读15分钟
两数之和¶
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
来源: LeetCode第1题
代码实现¶
其实是非常简单的一道题目。如果没有接触过哈希表的话，首先想到的是双层循环暴力解决，不过无疑效率是非常低的，利用哈希表我们可以将时间复杂度降到 O(n)。
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let map = {};
for (let i = 0; i < nums.length; i++) {
if (map[nums[i]] !== undefined) {
return [i, map[nums[i]]];
}
else {
map[target - nums[i]] = i;
}
}
};
三数之和¶
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
来源: LeetCode第15题
思路分析¶
咋一看，这一题也可以用三重循环来暴力解决，当然这也是可以实现的，不过显然可以用其他的方式优化。
方式一: 哈希表：我们先看看哈希表怎么来解决这个问题。首先遍历数组，拿到数组的一项 nums[i]， 剩下的问题就是找到和为 0 - nums[i] 的两个数啦，对于数组中后面的元素就可以使用两数之和建立哈希表的方式来完成——时间复杂度不好
方式二: 双指针: 还有一种方式是先排好序，然后在寻找和为 0 - nums[i] 的两个数的时候，通过双指针来完成，一个指针指向 nums[i + 1], 另一个指针指向 nums 中最后一个元素，计算出两个指针所指元素的和，如果和小于 0 - nums[i]，则移动把较小元素的指针向后移，反之把较大元素的指针向前移，以达到逼近结果的效果。
接下来我们来一一实现:
代码实现¶
哈希表的方式：很可惜的是，这段程序一直没有通过 LeetCode 的时间测试，总是卡在最后三个用例，不过也算是用哈希表正确地实现了功能，有兴趣的同学可以自己继续尝试一下。
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
let res = [];
let set = new Set();
for(let i = 0; i < nums.length - 2; i++) {
if(i >= 1 && nums[i] === nums[i - 1]) {
continue;
}
// map 的 key 表示: 其他两个数都准备好了哈，就差这一个key了。
let map = {};
for(let j = i + 1; j < nums.length; j++) {
if(map[nums[j]]) {
let arr = [nums[i], nums[j], 0 - nums[i] - nums[j]]
arr.sort();
// Set 没法对引用类型去重，因此采用这样的方式处理去重问题
set.add(arr.toString())
} else {
// 两个数都准备好了，看第三个数在不在，把 key 设成第三个数鸭
map[0 - nums[i] - nums[j]] = 1;
}
}
}
set.forEach(item => {
// 还原数组
res.push(item.split(','));
});
return res;
};
接下来是官方非常推崇的一种方法: 双指针。我试着实现了一波，成功通过了测试，并且超过 JavaScript 中 99% 的用户。
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
// 首先要排序
nums.sort((a, b) => a - b);
let map = {}, res = [];
// 优化1: 数组全正或全负，直接返回[] 看三数的和要求是0还是其他值
if(nums[0] > 0 || nums[nums.length - 1] < 0) {
return [];
}
for (let i = 0; i < nums.length - 2; i++) {
if(i >= 1 && nums[i] === nums[i - 1]) {
continue;
}
// 优化2: 遇到正数，后面不用看了，不会有等于0的情况了
if(nums[i] > 0) {
break;
}
let target = 0 - nums[i];
let start = i + 1;
let end = nums.length - 1;
// 开始双指针处理
while(start < end) {
let cur = nums[start] + nums[end];
//判断当前的和与目标值的差
if (cur < target) {
start++;
}
else if(cur > target) {
end--;
}
// 如果三数和满足要求
else {
res.push([nums[i], nums[start], nums[end]]);
// 去重，非常重要(减少复杂度)
while(start < end && nums[start + 1] === nums[start]) {
start ++;
}
while(start < end && nums[end - 1] === nums[end]) {
end--;
}
start ++;
end --;
}
}
}
return res;
};
四数之和¶
给定一个包含 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] ]
来源: LeetCode第18题
代码实现¶
有了三数之和问题作铺垫，解决这个问题简直是小菜一碟了。
优化：应该初始化去重一下，避免在循环内部跳过 continue 语句。
算法复杂度： 好的时候 N2 最差 N3
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function(nums, k) {
// 数组排序
nums.sort((a, b) => a - b);
let res = [];
for (let i = 0; i < nums.length - 3; i++) {
// 重复值跳过
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
for(let index = i + 1; index < nums.length - 2; index++) {
// 重复值跳过
if(index > i + 1 && nums[index] === nums[index - 1]) {
continue;
}
// 外部是双层循环，内部获取目标值，然后双指针处理
let target = k - nums[i] - nums[index];
let start = index + 1, end = nums.length - 1;
// 开始双指针处理
while(start < end) {
let cur = nums[start] + nums[end];
if(cur < target) {
start++;
}
else if(cur > target) {
end--;
}
else {
res.push([nums[i],nums[index],nums[start], nums[end]]);
// 去重
while(start < end && nums[start + 1] === nums[start]) {
start++;
}
while(start < end && nums[end - 1] === nums[end]) {
end--;
}
start++;
end--;
}
}
}
}
return res;
};