力扣-1. 两数之和

https://leetcode.cn/problems/two-sum/

「找到另一个数字，使两个数字满足某种关系」

核心只有三个动作：

1. 算出我需要什么
2. 去 Map 里找
3. 找不到就把当前元素存进去

最值得记住的一句话就是：

不要每次都重新查找；可以把之前的信息保存下来。

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

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

    if (map.has(need)) {
      return [map.get(need)!, i]
    }

    map.set(current, i)
  }

  return []
}

时间复杂度：O(n)，空间复杂度：O(n)。