两数之和

LeetCode 第 1 题两数之和的哈希表解法。

#tech / dev / frontend #type / concept #status / growing #resource / algorithm #source / leetcode #algo / hash #ds / array

[!info] related notes

所属 MOC: 算法面试题型 MOC, 算法面试模式 MOC

前置概念: [[ds/hash|哈希表]]

并列概念: [[two-sum-ii-input-array-is-sorted|两数之和 II]], [[three-sum|三数之和]]

两数之和

这篇笔记回答一个问题：如何在数组中找到两个数，使它们的和等于目标值。

题目

给定一个整数数组 nums 和一个目标值 target，返回两个数的下标，使它们相加等于 target。每组输入只对应一个答案，且不能重复使用同一元素。

核心思路

用哈希表记录已经遍历过的值和下标。每到一个新元素时，先看 target - 当前值是否在表中，在就找到了答案，不在就把当前值存入表。

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

代码实现

function twoSum(nums, target) {
  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 [];
}

边界情况

数组长度小于 2：无解
没有符合条件的两个数：返回空数组
同一个元素不能用两次：哈希表先查后存，天然避免

最小例子

twoSum([2, 7, 11, 15], 9); // [0, 1]
twoSum([3, 2, 4], 6);      // [1, 2]
twoSum([3, 3], 6);         // [0, 1]