LeetCode 两数之和：JavaScript Map 解法

题目

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

思路

最直接的想法是两层循环，外层固定一个数，内层找另一个，能过但是 O(n^2)。

优化的切入点在于：内层循环其实是在做一件很明确的事——查找「target 减去当前值」是否出现过。既然是查找，就该用适合查找的结构。哈希表把查找从 O(n) 的遍历降到 O(1)，整体就变成 O(n)，代价是多用 O(n) 的空间。这是典型的用空间换时间。

还有个关键点是「出现过」这三个字。不需要预先把整个数组存进哈希表，只在遍历过程中边查边存即可：查的是当前元素之前的那些数。这样天然避免了同一个元素被用两次的问题，也不会漏解——任意一对答案里，遍历到后出现的那个元素时，先出现的那个必然已经在表里了。

题解一

这个版本用普通对象当哈希表，存的是「已经见过的数字」到它下标的映射。

function twoSum(nums, target) {
  let map = {};
  for (let i = 0; i < nums.length; ++i) {
    const rest = target - nums[i];
    if (map[rest] !== undefined) {
      return [map[rest], i];
    }
    map[nums[i]] = i;
  }
  //
  return [];
}

循环里的顺序不能颠倒：先查再存。如果先存后查，遇到 target 是当前值两倍的情况，比如 target 为 6 而当前值为 3，刚存进去的自己会立刻被查到，返回两个相同的下标，这违反了「同一个元素不能重复出现」。

判断条件用的是 map[rest] !== undefined 而不是简单的 if (map[rest])。这一点很重要：如果匹配元素的下标恰好是 0，那么 map[rest] 取到的值是 0，在 if 里是假值，会被当成没找到。所以必须显式跟 undefined 比较。

用普通对象还有一个隐患：对象的键会被转成字符串，而且原型链上本来就有 constructor、toString 这些属性。如果数组里的数字正好跟某个原型属性名撞上（数字场景下不会，但泛化到其他类型就有风险），map[rest] 会取到原型上的值，产生误判。用 Object.create(null) 创建无原型的对象可以规避。

题解二优化利用 Map

这个版本换了两个地方：容器用 Map，以及存进去的内容变了。

Map 相比普通对象的好处是键保持原始类型不做字符串转换、有 has 方法可以干净地判断存在性（不用担心值为 0 的坑）、也没有原型链污染的问题。查找同样是 O(1)。

更值得注意的是第二个改动：这里存的不是当前数字，而是 target - n，也就是「我需要的那个搭档」。于是每次拿到新数字，直接问「有没有人在等我」，逻辑上比上一个版本更顺——上一个版本是存自己、查搭档，这个版本是存搭档、查自己。两者等价，都是一次遍历 O(n)。

function twoSum(nums, target) {
  const map = new Map();

  for (var i = 0; i < nums.length; i++) {
    var n = nums[i];
    if (map.has(n)) {
      return [map.get(n), i];
    }
    map.set(target - n, i);
  }
}

同样是先 has 再 set，顺序不能反，道理和上面一样。

这个版本没写循环结束后的返回语句，函数会隐式返回 undefined。题目保证有唯一解所以能过，但严格来说加一个 return [] 更稳妥，调用方拿到的类型才是一致的。

最后提一下重复元素。存的时候后来的会覆盖先前的同键值，但这不影响正确性：题目保证只有一个答案，而且不管配上哪个下标，值都是对的。如果题目改成要返回所有满足条件的下标对，就不能这么覆盖了，得把值改成下标数组。

题目

思路

题解一

题解二优化 利用 Map

题解二优化利用 Map