Javascript新法解旧题之【两数之和】
题目如下：
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。
示例
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
leetCood地址：两数之和
题目不难理解，首先一上来我们马上就能想到使用两个循环解决的办法。
遍历所有组合，找到符合要求的组合就行。
双层循环
代码如下：
const twoSum = (nums, target) => {
let arr = [];
for(let i = 0; i < nums.length; i++) {
for(let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
arr = [i, j];
break;
}
}
}
return arr;
};
两个循环，时间复杂度为O(N*N)。
leetCode测试数据如下：
我的提交执行用时已经战胜 17.42 % 的 javascript 提交记录
在第二个循环中，我们只是要寻找目标值是否在数组里，因此可想到javascript中的一个方法----indexOf。
indexOf 用法
代码可改写如下：
const twoSum = (nums, target) => {
let a, b;
for(let i = 0; i < nums.length; i++) {
b = nums.indexOf(target - nums[i]);
if(b > -1 && b !== i) {
a = i;
break;
}
}
return [a, b];
};
但是 Array 的 indexOf 方法实际上是对数组再遍历一次，虽然在写法上有优化，但是实际时间复杂度还是O(N*N)。
在时间复杂度上做优化，我们需要解决一个问题，如何快速地在数组中检索值？使用 indexOf 其实已经在数据中检索特定值的思路上了。只不过 indexOf 内部还是对数组进行循环检索，因此并没有达到更快的要求。在这方面， hash表 可以帮助到我们。
什么意思呢？比如我们有一个对象 obj = { ..., a: 1} ，当我们取值 Obj.a 时，是个直接寻址的过程，因此效率是很高的。回到题目，在这个思路上改进我们的代码：
使用对象索引
const twoSum = (nums, target) => {
let mapObj = {};
let res = [];
nums.forEach((e, i) => mapObj[e] = i);
for(let i=0;i<nums.length;i++) {
let j = mapObj[targer - nums[i]];
if(j && j !== i) {
res = [i, j];
break;
}
}
return res;
};
我们创建一个对象，并给它赋值，对象的键值是我们想要检索的值，对象的值是在数组中的索引。
虽然多了创建对象这一过程，但是我们少了一层循环。
然后我们来看执行效率：
我的提交执行用时已经战胜 86.24 % 的 javascript 提交记录。
从 17.42 % 到 86.24 %，可以说是个质的飞跃。
es6 中，给我们提供了一个新对象 Map，在这里就可以拍上用途。
使用 map
const twoSum = (nums, target) => {
let map = new Map();
let res = [];
nums.forEach((e, i) => map.set(e, i));
for(let i=0;i<nums.length;i++) {
let j = map.get[targer - nums[i]];
if(j && j !== i) {
res = [i, j];
break;
}
}
return res;
};
最终使用 Map 优化的代码，让我们战胜了 97.21 % 的提交。
