跳到主要内容

补数映射

如何一次遍历求出两数之和？​

  • 目标: 找到满足 a + b = target 的两个下标;
  • 映射: 表中记录"已遍历过的值 → 下标";
  • 命中: 遍历到 b 时, 若表中已有 target - b, 说明 a 已经出现过;
  • 顺序: 先查表再登记, 保证不会用到自身下标;
function twoSum(nums: number[], target: number): number[] | undefined {
  const seen = new Map<number, number>(); // 值 → 下标
  for (let i = 0; i < nums.length; i++) {
    const completer = target - nums[i];
    if (seen.has(completer)) return [seen.get(completer)!, i];
    seen.set(nums[i], i);
  }
}

为什么这种做法只需要一次遍历？​

  • 朴素做法: 双重循环枚举所有数对, 时间 O(n²);
  • 补数思想: 遇到 a 时它需要配对的 target - a 已经确定, 提前登记即可;
  • 遇到 b 时, a 已经登记过, 因此任意一对只会被检查一次;
  • 复杂度: 时间 O(n), 空间 O(n);