数组的应用——真题归纳与解读|算法篇

哈希解法的不变量是：进入第 i 轮时，seen 只保存区间 [0, i) 的值及下标。因此命中补数时，它一定来自不同元素；未命中才写入当前值。原文使用对象并用 !== undefined 判断，会把“索引值是否存在”和“属性值是否为 undefined”混在一起，使用 Map.has() 更直接。

function twoSum(nums, target) {
  const seen = new Map()
  for (let i = 0; i < nums.length; i += 1) {
    const need = target - nums[i]
    if (seen.has(need)) return [seen.get(need), i]
    seen.set(nums[i], i)
  }
  return []
}

每个元素最多查询和写入一次，期望时间 O(n)、额外空间 O(n)。若要求全部不重复下标组合，Map<number, number> 不够，需要保存每个值的下标列表或采用另一套去重契约；若输入含浮点数，还要先确认能否直接用精确相等比较。

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

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

示例:

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

一个“淳朴”的解法

这道题相信很多同学看一眼就很快能得出一个最基本的思路：两层循环来遍历同一个数组；第一层循环遍历的值记为 a，第二层循环时遍历的值记为 b；若 a+b = 目标值，那么 a 和 b 对应的数组下标就是我们想要的答案。

对“淳朴”解法的反思

大家以后做算法题的时候，要有这样的一种本能：当发现自己的代码里有两层循环时，先反思一下，能不能用空间换时间，把它优化成一层循环。

因为两层循环很多情况下都意味着 O(n^2) 的复杂度，这个复杂度非常容易导致你的算法超时。即便没有超时，在明明有一层遍历解法的情况下，你写了两层遍历，面试官对你的印象分会大打折扣。

空间换时间，Map 来帮忙

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

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

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

我们以 nums = [2, 7, 11, 15] 这个数组为例，来模拟一下这个思路：

第一次遍历到 2，此时 Map 为空：

以 2 为 key，索引 0 为 value 作存储，继续往下走；遇到了 7：

计算 targetNum 和 7 的差值为2，去 Map 中检索 2 这个 key，发现是之前出现过的值：

那么 2 和 7 的索引组合就是这道题的答案啦。

键值对存储我们可以用 ES6 里的 Map 来做，如果图省事，直接用对象字面量来定义也没什么问题

编码实现

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = function(nums, target) {
    // 这里我用对象来模拟 map 的能力
    const diffs = {}
    // 缓存数组长度
    const len = nums.length
    // 遍历数组
    for(let i=0;i<len;i++) {
        // 判断当前值对应的 target 差值是否存在（是否已遍历过）
        if(diffs[target-nums[i]]!==undefined) {
            // 若有对应差值，那么答案get！
            return [diffs[target - nums[i]], i]
        }
        // 若没有对应差值，则记录当前值
        diffs[nums[i]]=i
    }
};

tips：这道题也可以用 ES6 中的 Map 来做，你试试呢？