两数之和

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]。

我的解题过程

第一次尝试：暴力解法

一开始想到的就是暴力解法，使用两层循环遍历数组，找到符合条件的两个下标。

虽然这个方法不是最优的，但是思路很直观，就是把所有可能的组合都试一遍。外层循环固定第一个数，内层循环去找能配对的第二个数。

function twoSum(nums: number[], target: number): number[] {
  let fir;
  for (let i = 0; i < nums.length; i++) {
    fir = nums[i];
    for (let j = i + 1; j < nums.length; j++) {
      if (target === fir + nums[j]) return [i, j];
    }
  }
}

这个方法的问题是效率比较低，时间复杂度是 O(n²)，如果数组很大的话会比较慢。

优化思路：使用哈希表

后面想到可以优化一下，关键点在于：每次遍历到一个数时，我不需要再用一层循环去找它的配对，而是可以直接查找”差值”是否已经出现过。

具体来说就是：

• 用一个对象（哈希表）存储已经遍历过的数和它的下标
• 遍历数组时，计算 rest = target - nums[i]
• 如果这个 rest 已经在对象里了，说明找到了答案
• 如果没找到，就把当前的数存进对象，继续往后找

这样只需要遍历一次数组就行了，时间复杂度降到 O(n)。

function twoSum(nums: number[], target: number): number[] {
  const map: Record<number, number> = {};

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

    // 可能存在0
    if (map[rest] !== undefined) {
      return [map[rest], i];
    }

    map[nums[i]] = i;
  }

  return [];
}

小结

这道题是典型的”空间换时间”的例子。虽然用了额外的空间（对象），但是把时间复杂度从 O(n²) 优化到了 O(n)，这个交换是很值得的。

另外要注意一个小细节：判断对象里是否存在某个 key 时，要用 !== undefined，而不是简单的 if (map[rest])，因为可能存在值为 0 的情况。