Two Sum

找出两个数之和等于目标值的下标。

给定数组和目标值，返回两个下标，使它们对应的数之和等于目标值。关键不只是找到答案，还要在一趟遍历里保住原始下标。

ArrayHash Table

题目定位

虽然最优解通常是哈希，但它很适合建立一个面试习惯：先判断题目能否通过排序或顺序关系变成成对指针搜索。

关键观察

本质上是在做补数查询：遍历到 x 时，只要问 target - x 之前是否出现过。

目标复杂度

O(n) / O(n)

这题的解法思路怎么拆

从左到右遍历，把每个数都当成一次“补数查询”。

在存当前数字之前，先问 target - nums[i] 是否已经出现过。

如果出现过，直接返回之前的下标和当前下标。

否则把 nums[i] -> i 记下来，供后面的数字匹配。

拿一个例子顺一遍

例如 nums = [2, 7, 11, 15], target = 9。

先读到 2，发现补数 7 还没出现，所以先记录 2 -> 0。

再读到 7，它的补数 2 已经在表里，因此答案就是 [0, 1]。

参考实现

Python

def twoSum(nums, target):
    seen = {}

    for index, value in enumerate(nums):
        complement = target - value
        if complement in seen:
            return [seen[complement], index]
        seen[value] = index

    return []

TypeScript 版本

TypeScript

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>();

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

    if (seen.has(complement)) {
      return [seen.get(complement)!, index];
    }

    seen.set(value, index);
  }

  return [];
}