两数之和

在数组中快速找到两个数，他们相加之和等于某个确定的值

题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

思路

循环 nums，target 减去当前项，获取到差，然后在余下的数组项里面寻找与差相等的项。

解题

方案一：使用indexOf()

var twoSum = function(nums, target) {
  for (let i = 0, len = nums.length; i < len; i++) {
    const aim = nums.indexOf(target - nums[i], i + 1);
    if (aim > -1) return [i, aim];
  }
};

方案二：使用 hash 表

用空间换速度，通过构建一张 hash 表，可以使用键名进行查询，相对于indexOf()遍历所有元素检查，效率更高，数组长度越大，提升越明显。

var twoSum = function(nums, target) {
    const temp = {};
    for(let i = 0, len = nums.length; i < len; i++){
        temp[nums[i]] = i;
    }
    for(let i = 0, len = nums.length; i < len; i++){
        const aim = target - nums[i];
        if(temp[aim] && temp[aim]!==i) return [i,temp[aim]]
    }
};

方案三：使用 Map（最优解）

在存在大量增删操作的场景中，Map 相较于 Object 的性能更优。

var twoSum = function(nums, target) {
    const temp = new Map();
    for (let i = 0, len = nums.length; i < len; i++) {
        temp.set(nums[i], i);
    }
    for (let i = 0, len = nums.length; i < len; i++) {
        const aim = target - nums[i];
        if (temp.has(aim) && temp.get(aim) !== i) return [i, temp.get(aim)];
    }
};

不过这两种方式的结果在某些情况下的输出结果是不一样的，比如当一个数字多次出现时，因为方案一在遇到第一个符合的项时，就退出循环了，所以取到的是第一个符合的项的 index，而第二种和第三种方式使用的是 hash 表，不能存在相同的键名，相同的数字会覆盖键值（index），所以最后取到的是最后一个符合的项的 index。