两数之和

力扣 1: 两数之和

能用双指针吗？ ​

这道两数之和可以说是力扣版的 Hello World 了，前一篇，我们已经解决了三数之和，同样的解法我们能解这道题吗？

其实一直一来，我感觉都被这两道题的标题“骗”了，两数之和求的是一个目标为指定数的 target，这其实就是第三个数，只是这个第三个数不会变动。

而三数之和求的是和为 0，我们在解三数之和的时候也确实转换成两数之和在做。

所以，两数之和就是三数之和的一个子问题。只是要求的返回结果不太一样，返回索引值。而且第一题题目保证会有且只有一个答案。

由于初始数组同样没有排序，我们如果还是想用双指针，时间复杂度上考虑会得不偿失。我们可以利用空间换时间的思想，用哈希表来加速查询。

当然 n^2 的暴力查询的代码是最简单的，而哈希表的方法只需要 n 的复杂度。

哈希表 ​

基本原理是，当前数字如果是答案，那么另一个数字一定会在会须遍历时出现，所以我们把另一数组和当前索引记录到哈希表中，后续循环中，如果数字在哈希表中存在，我们取出索引和当前索引一起返回即可。

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

  for (let i=0; i<nums.length; i++) {
    if (m.has(nums[i])) {
      return [m.get(nums[i]), i]
    }
    m.set(target-nums[i], i)
  }

  return [] // never
};

我们在循环内部直接返回了，由于题目的保证，最后的 return 是执行不到的。