IT 面试题库

如何用哈希表在 O(n) 时间内解决「两数之和」?请说明思路、复杂度并给出代码

初级简答题前端开发工程师后端开发工程师算法工程师哈希表数组两数之和

题目

考察哈希表以空间换时间、一次遍历查找补数的技巧

参考答案

内容深度:适中 · 含示例/代码 · 来源:外部链接 · 未复核 · 54 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

思路

复杂度

代码(JavaScript)

function twoSum(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (map.has(need)) return [map.get(need), i];
    map.set(nums[i], i);
  }
  return [];
}

上面代码先算需要的补数 need,若已出现则直接返回两个下标,否则把当前值记下;由于先查后存,保证同一元素不会被重复使用。

练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题