两数求和问题

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例: 给定 $nums = [2, 7, 11, 15], target = 9$
因为 $nums[0] + nums[1] = 2 + 7 = 9$ 所以返回 $[0, 1]$

一个“淳朴,暴力”的解法：

两层循环来遍历同一个数组；第一层循环遍历的值记为 a，第二层循环时遍历的值记为 b；若 a+b = 目标值，那么 a 和 b 对应的数组下标就是我们想要的答案。

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

上面的解法是2层循环！每一层都是n，那么时间复杂度就是$n*n$ = $O(n^2)$，空间复杂度则只占用了2个（i,j）固定内存！不会随着代码的进行而产生变化!空间复杂度为$O(2)$!这是一个典型时间换空间的解法，但是在大部分正常情况下，我们认为运算的时间是比空间更加重要的！

空间换时间，Map 来帮忙

拿我们这道题来说，其实二层遍历是完全不必要的。

大家记住一个结论：几乎所有的求和问题，都可以转化为求差问题。 这道题就是一个典型的例子，通过把求和问题转化为求差问题，事情会变得更加简单。

我们可以在遍历数组的过程中，增加一个 Map 来记录已经遍历过的数字及其对应的索引值。然后每遍历到一个新数字的时候，都回到 Map 里去查询 targetNum 与该数的差值是否已经在前面的数字中出现过了。若出现过，那么答案已然显现，我们就不必再往下走了。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    let map = new Map();
    for (let i = 0; i < nums.length; i++) {
        map.set(nums[i], i)
    }
    for (let i = 0; i < nums.length; i++) {
        let has = map.has(target-nums[i])
        let getMapI = map.get(target-nums[i])
        if(has&&getMapI!==i){
            return [i,map.get(target-nums[i])]
        }
    }
    return []
};

可以看到这种速度的确快了很多！