两数之和各种解：
var twoSum = function(nums, target){
// 这是用 map，这里还挺合适的
// var map = new Map();
// for(var i = 0; i< nums.length; i++) {
// if(map.has(target - nums[i])) {
// return [map.get(target - nums[i]), i]
// } else {
// map.set(nums[i], i) // 索引为value
// }
// }
// 这是用 Set，这里不是最合适的，虽然能拿到结果，但是得indexof一下
// var obj = new Set();
// for(var i = 0; i< nums.length; i++) {
// if(obj.has(target-nums[i])) {
// return [nums.indexOf(target-nums[i]), i];
// } else{
// obj.add(nums[i])
// }
// }
// 这是一种常规的暴力
// for(let i = 0 ; i<nums.length; i++) {
// for(let j = i+1; j < nums.length; j++) {
// if(nums[i]+nums[j] === target) {
// return [i, j];
// }
// }
// }
// 这是一种比较有意思的暴力写法，巧妙利用随机数
// while(true) {
// var i = Math.floor(Math.random() * nums.length)
// var j = Math.floor(Math.random() * nums.length)
// if(i < j && nums[i] + nums[j] === target)
// return[i, j]
// }
// 双指针比较适合排序过的数组，这里不太合适，还得indexof找索引
// var L = 0, R = nums.length - 1;
// var res = [];
// while(L < R) {
// if(nums[L] + num[R] === target) {
// res.push(nums[L], nums[R])
// }
// if(nums[L] + num[R] > target) {
// R--
// }
// if(nums[L] + num[R] < target) {
// L--
// }
// }
// return [nums.indexOf(res[0]), nums.indexOf(res[1])]
}
一、前言
不知不觉，近两年大厂将算法作为衡量候选人的重要指标。如果算法不过关，很多大厂会将你拒之门外。如果你想提升自己的基本功或今后准备进入大厂，那么开始觉悟准备好头秃吧 :)，让我们从这篇算法题开始。
刷过Leet-code（力扣）的同学知道，两数之和是开启算法的第一题，比较简单。但遇到三数之和、四数之和、n数之和你是同样否有思路呢？
其实这类题的解题都有共性，本文将教大家从中寻找规律，让麻麻以后再也不用担心你的学习。
本文我只举例两类的算法，其他方法暂不介绍，这样方便大家学习和记忆。通过本文，你将学会：
- 暴力算法
- 排序+双指针算法
- 求解n数之和类型题
建议：先码后看、自己跑一跑文中代码
二、暴力算法
【题目1】两数之和（难度：简单）
> 两数之和：https://leetcode-cn.com/problems/two-sum/
给定一个整数数组 nums 和一个目标值target，请你在该数组中找出和为目标值的那 **两个** 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
方法：
最简单的也就是 暴力算法。
var twoSum = function(nums, target) {
for(let i = 0 ; i< nums.length; i++) {
for(let j = i+1; j < nums.length; j++) {
if(nums[i]+nums[j] === target) {
return [i, j];
}
}
}
};
使用两层循环，外层循环计算当前元素与 target 之间的差值，内层循环寻找该差值，若找到该差值，则返回两个元素的下标。
时间复杂度：O(n^2)。
好，上面我们使用了暴力算法来算出了两数之和。 那么接下来我们来类推下，如何计算三数之和、四数之和呢？接着往下看。
【题目2】三数之和（难度：中等）
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
方法：
根据两数之和暴力算法类推，三数之和 暴力算法：
var threeSum = function(nums) {
let res = [];
nums.sort((a, b) => a-b);
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
for (let k = j + 1; k < nums.length; k++) {
if (nums[i] + nums[j] + nums[k] === 0) {
res.push([nums[i], nums[j], nums[k]])
}
}
}
}
return res;
}
上面我们使用三层循环，时间复杂度：O(n^3)。我们跑一下结果得到如下：
嗯，是的，这还不对，我们需要对结果进行去重，这也是三数之和和两数之和同样使用暴力算法中不一样的地方。可能这时候你会想到直接将结果像下面这么处理一下不就行了嘛。
Array.from(new Set(res))
但这是二维的数组，算是去重上的一个小难点。所以这里我们利用 hash 方法来去重，小白可以先来简单了解下去重：
// 初级版本（一维）
function unique(arr) {
let tempObj = new Set();
let res = [];
for(let i =0;i<arr.length; i++) {
if(!tempObj.has(arr[i])) {
res.push(arr[i]);
tempObj.add(arr[i]);
}
}
return res;
}
uinque([1,1,2]); // [1, 2]
-----------分割线
// 高级版本（多维）
function unique(arr) {
let res = [];
let tempObj = new Set();
for(let i =0;i<arr.length; i++) {
// 每个元素转为字符串
let tempStr = arr[i] + '';
if(!tempObj.has(tempStr)) {
res.push(arr[i]);
tempObj.add(tempStr);
}
}
return res;
}
// 试一下：
unique([[1,2],[1,2], 2,3]); // [[1,2], 2, 3]
unique([[1,[1,2]],[1,[1,2]], 2,3]); // [[1,[1,2]], 2, 3]
// 嗯，ojbk！
好，接下来我们继续！用 hash 去重来处理前面的三数和的去重：
// 原始版本
function unique(arr) {
let res = [];
let tempObj = new Set();
for(let i =0;i<arr.length; i++) {
// 每个元素转为字符串
let tempStr = arr[i] + '';
if(!tempObj.has(tempStr)) {
res.push(arr[i]);
tempObj.add(tempStr);
}
}
return res;
}
var threeSum = function(nums) {
let res = [];
nums.sort((a, b) => a-b);
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
for (let k = j + 1; k < nums.length; k++) {
if (nums[i] + nums[j] + nums[k] === 0) {
res.push([nums[i], nums[j], nums[k]])
}
}
}
}
return unique(res);
}
-------------------- 分割线
// 将上面去重方法合成下面可能会显得你更“高级前端开发”
var threeSum = function(nums) {
let res = [];
+ let tempObj = new Set();
nums.sort((a, b) => a-b);
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
for (let k = j + 1; k < nums.length; k++) {
if(nums[i]+nums[j]+nums[k] === 0) {
+ let tempRes = [nums[i] + nums[j] + nums[k]];
+ let tempStr = tempRes + '';
+ if (!tempObj.has(temStr)) {
+ res.push(tempRes);
+ tempObj.add(tempStr);
+ }
}
}
}
}
return res;
}
well，现在我们完成了三数相加的暴力算法！ 接下来我们来以此类推完成一道四数之和。
【题目3】四数之和（难度：中等）
给定一个包含 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]
]。
方法：
没有什么是暴力解不开的 :)，先不管去重，先拿到结果：
var fourSum = function(nums, target) {
let res = [];
nums.sort((a, b) => a-b);
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
for (let k = j + 1; k < nums.length; k++) {
for(let l = k + 1; l < nums.length; l++){
if(nums[i]+nums[j]+nums[k]+nums[l] === target) {
res.push([nums[i], nums[j], nums[k], nums[l]]);
}
}
}
}
}
return res;
}
接下来，再去去重:
// 去重方法
function unique(arr) {
let res = [];
let tempObj = new Set();
for(let i =0;i<arr.length; i++) {
// 每个元素转为字符串
let tempStr = arr[i] + '';
if(!tempObj.has(tempStr)) {
res.push(arr[i]);
tempObj.add(tempStr);
}
}
return res;
}
var fourSum = function(nums, target) {
let res = [];
nums.sort((a, b) => a-b);
for (let i = 0; i < nums.length - 3; i++) {
for (let j = i + 1; j < nums.length - 2; j++) {
for (let k = j + 1; k < nums.length - 1; k++) {
for(let l = k + 1; l < nums.length; l++){
if(nums[i]+nums[j]+nums[k]+nums[l] === target) {
res.push([nums[i], nums[j], nums[k], nums[l]]);
}
}
}
}
}
+ return unique(res);
}
没有什么是暴力算法解不开的，什么？你说超时了！先不管，反正这题我算是会做了。
就这？太low了，那我们下面来讲讲“高级开发”的解法吧。
三、排序+双指针
知识小讲堂：什么是指针？
凡是数组的题目，大部分都是利用双指针去解决问题。
双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。
换言之，双指针法充分使用了数组有序这一特征，从而在某些情况下能够简化一些运算。
1、对撞指针，是指在有序数组中，将指向最左侧的索引定义为左指针(left)，最右侧的定义为右指针(right)，然后从两头向中间进行数组遍历。
对撞数组适用于有序数组，也就是说当你遇到题目给定有序数组时，应该第一时间想到用对撞指针解题。
快慢指针，也是双指针，但是两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针（fast）和慢指针（slow），两个指针以不同的策略移动，直到两个指针的值相等（或其他特殊条件）为止，如fast每次增长两个，slow每次增长一个。
先大概了解下什么是指针，如果感到模糊，没关系，做几道题就会啦！
从最简单的题开始。
【题目1】两数之和（难度：简单）
还是这道简单的题目：
给定一个整数数组 nums 和一个目标值target，请你在该数组中找出和为目标值的那 两个 整数，并返回 他们的数组下标 满足条件的数组。（由于这题太简单，为了学习双指针的使用，此处我们将题目稍作修改）
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
满足要求的数组为：
[2，7]
方法：
解题思路： 先来心中默念3遍这句话：
凡是数组的题目，基本上都是利用双指针去解决问题！
凡是数组的题目，基本上都是利用双指针去解决问题！
凡是数组的题目，基本上都是利用双指针去解决问题！
没错，这道题就是使用双指针！一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。
如上图，左边就是左指针，右边是右指针。
- 如果两个指针指向元素的和 sum == target，那么得到要求的结果；
- 如果 sum > target，移动较大的元素，使 sum 变小一些；
- 如果 sum < target，移动较小的元素，使 sum 变大一些。
数组中的元素最多遍历一次，时间复杂度为 O(N)。只使用了两个额外变量，空间复杂度为 O(1)。
var twoSum = function(nums, target) {
let res = [];
nums.sort((a, b) => a - b); // 让数组成为有序排序
let L = 0; // 定义左指针
let R = nums.length - 1; // 定义右指针
while(L < R) {
const sum = nums[L] + nums[R];
if(sum === target) {
res.push(nums[L]);
res.push(nums[R]);
break;
} else if(sum > target) {
R--;
} else if(sum < target) {
L--;
}
}
return res;
};
twoSum([3, 1, 7], 8); // [1, 7]
OK，是不是很好理解。接下来继续。
【题目2】三数之和（难度：中等）
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
方法：
还是这句话，心中默念：凡是数组的题目，基本都是利用双指针去解决问题！
1、拿到原数组：
2、排序：
nums.sort((a, b) => a - b);
3、设置左右指针：
for(let i = 0;i < len; i++) {
// 设置左右指针
let L = i + 1;
let R = len - 1;
}
4、从左往右遍历，将nums[i]设置为第一个元素，L为左侧第一个元素，R为当前数组右侧的第一个元素
5、比较 sum（nums[i] + nums[L] + nums[R]）和 target 的大小
- 如果sum < 0，左指针往右移
- 如果sum > 0，右指针往左移
代码如下：
var threeSum = function (nums) {
let res = [];
if(nums === null && nums.length < 3) return res;
let len = nums.length;
nums.sort((a, b) => a - b); // 老样子，要使用双指针，先成为有序数组
for(let i = 0;i < len; i++) {
if(nums[i] > 0) break;
if(i>0 && nums[i] === nums[i-1]) continue; // 去重，跳过本次循环
// 设置左右指针
let L = i + 1;
let R = len - 1;
while(L < R) {
const sum = nums[i] + nums[L] + nums[R];
if(sum === 0) {
res.push([nums[i], nums[L], nums[R]]);
while(L < R && nums[L] === nums[L+1]) L++; // 去重
while(L < R && nums[R] === nums[R-1]) R--; // 去重
L++;
R--;
}
else if(sum < 0) L++;
else if(sum > 0) R--;
}
}
return res;
}
这类问题其实就是这样，掌握一个，其他的都是类似解法。需要注意的就是去重。 从上面我们我们可以类推到四数之和，接着往下看！
【题目3】四数之和（难度：中等）
给定一个包含 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]
]。
方法：
排序+双指针
var fourSum = function (nums, target) {
let res = [];
let len = nums.length;
// 关键1：排序
nums.sort((a, b) => a-b);
if(len < 4) return res;
for(let i = 0; i<len-3; i++){
// 关键点2：去重
if(i > 0 && nums[i] === nums[i-1]) continue;
for(let j = i+1; j<len-2; j++){
// 关键点5：去重
if(j > i+1 && nums[j] === nums[j-1]) continue;
let L = j + 1; // 双指针，最左边的
let R = len - 1; // 双指针，最右边的
while(L<R) {
let sum = nums[i]+nums[j]+nums[L]+nums[R];
if(sum === target) {
res.push([nums[i], nums[j], nums[L], nums[R]]);
while(nums[L] === nums[L+1]) L++; // 去重
while(nums[R] === nums[R-1]) R--;// 去重
L++;
R--;
} else if(sum > target) {
R--;
} else if(sum < target) {
L++;
}
}
}
}
return res;
}
四、总结
关键点：排序、设置左右指针、去重。 这类题目就是这样，掌握一个其他的都是类推，大家刷算法的时候也可以按照类型来，质量大于数量。
以上。
