我们现在要开始做题啦！

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

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

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

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

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

⚡ 30 秒速记

• 暴力枚举两下标是 O(n²)；哈希表把“找另一个数”降为期望 O(1)，总时间 O(n)、空间 O(n)
• 每轮先算 need = target - nums[i] 并查询已扫描前缀，再写当前值，才能保证不重复使用同一元素
• Map 的键可安全表示数字；普通对象会字符串化键，还要处理原型属性，不是更稳的默认选择
• 重复数字是否合法取决于下标：[3, 3] 可组成 6，只要它们来自两个位置
• 返回一组、全部组合或不存在时的结果必须先约定，不能让实现细节替题目决定契约

两数之和可以用 Map 记录“已遍历的值到下标”，把暴力枚举的 O(n²) 优化为期望 O(n)。 遍历到 nums[i] 时，先查询补数 target - nums[i]，未命中再写入当前值，这样不会重复使用同一个元素。重复数字本身没问题，例如两个不同位置的 3 可以组成 6。额外空间是 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，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。