两数之和

问题描述

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

答案

function twoSum(nums: number[], target: number): number[] {
  const map = new Map()
 
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i]
    if (map.has(complement)) {
      return [map.get(complement), i]
    }
    map.set(nums[i], i)
  }
 
  return [] // 没有找到答案
}

• 一遍哈希表（One-pass Hash Table）
  • 指只需要遍历一次数组，同时使用哈希表存储和查找的解法
• 空间换时间（Space-Time Trade-off）
  • 通过增加空间复杂度（使用哈希表存储数据）
  • 来降低时间复杂度（从O(n²)降到O(n)）
• 查找表法（Look-up Table）
  • 使用哈希表作为查找表
  • 将查找时间从O(n)降低到O(1)