我们现在要开始做题啦！

万里长征第一步，仍然是数组。 单纯针对数组来考察的题目，总体来说，都不算太难——数组题目要想往难了出，基本都要结合排序、二分和动态规划这些相对复杂的算法思想才行。

咱们本节要解决的正是这一类“不算太难”的数组题目——并不是只有难题才拥有成为真题的入场券，一道好题不一定会难，它只要能够反映问题就可以了。

本节所涉及的题目在面试中普遍具有较高的出镜率、同时兼具一定的综合性，对培养大家的通用解题能力大有裨益 。

相信这节你会学得很开心，在轻松中收获自己的第一份算法解题锦囊。

Map 的妙用——两数求和问题

⚡ 30 秒速记

• 暴力两层循环 O(n²)；用 Map 记「值 → 下标」，变成一次遍历 O(n)、空间 O(n)
• 求和转求差：看到 x 就去查 target - x 出现过没有
• 顺序必须是先查后存，Map 里只放当前下标之前的数，才不会自己配自己
• 用 Map.has() 判存在，别用对象加 if (obj[k])，下标 0 是假值
• [3, 3] 凑 6 是合法的，两个不同位置就行

两数之和的套路是拿空间换时间：一边遍历一边用 Map 记下见过的数和下标，每到一个数就去查它的「另一半」在不在。 比如 nums = [2, 7, 11, 15]、target = 9，到 7 时查 9 - 7 = 2，Map 里有，下标 0，直接返回 [0, 1]。顺序很关键，一定是先查再存，不然 [3, 3] 找 6 时第一个 3 会和自己配对。时间从 O(n²) 降到 O(n)，代价是 O(n) 的额外空间。

哈希解法的不变量是：进入第 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，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。