#1. 两数之和

LeetCode 原题链接

#题目描述

给定整数数组 nums 和目标值 target，找出和为 target 的两个元素并返回它们的下标。题目保证恰好存在一个答案，同一元素不能使用两次。

输入：nums = [2,7,11,15], target = 9
输出：[0,1]

#题型判断

遍历到 nums[i] 时，需要知道它的补数 target - nums[i] 是否已经出现。哈希表可以用平均 O(1) 时间完成查询，因此能把暴力枚举的 O(n²) 降为 O(n)。

#核心思路

哈希表保存“已经遍历过的数值 → 下标”：

1. 计算当前值需要的补数。
2. 若补数已在 Map 中，立即返回补数下标和当前下标。
3. 否则保存当前值，继续遍历。

必须先查找再存入，避免在 target === nums[i] * 2 时错误地重复使用当前元素。

#代码实现

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

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];

    if (indexByValue.has(complement)) {
      return [indexByValue.get(complement), i];
    }

    indexByValue.set(nums[i], i);
  }

  return [];
};

#复杂度与易错点

• 时间复杂度：O(n)。
• 空间复杂度：O(n)。
• 要用 Map.has() 判断是否存在，不能用 Map.get() 的真假值判断，因为下标 0 是合法答案。
• 题目要返回下标，不能先排序，否则会丢失原始下标。
• 数组允许出现重复值，Map 中保存最近下标不影响找到合法答案。