[LeetCode 题1] 两数之和

问题描述

给定一个整数数组 nums 和一个目标值 target，请找出数组中和为目标值的两个整数，并返回它们的数组下标。你可以假设每个输入都只有一个解，并且不能使用相同的元素两次。返回的答案可以以任意顺序给出。

示例

1. 输入: nums = [2, 7, 11, 15], target = 9 输出: [0, 1] 解释: 因为 nums[0] + nums[1] == 9，所以返回 [0, 1]。

2. 输入: nums = [3, 2, 4], target = 6 输出: [1, 2]

3. 输入: nums = [3, 3], target = 6 输出: [0, 1]

约束条件

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• 每个输入只会有一个解

跟进

你能否设计一个时间复杂度小于 O(n^2) 的算法？

解决方案

我们可以使用哈希表（在 JavaScript 中是对象或 Map）来存储数组中的元素及其对应的索引。这样可以在常数时间内检查当前元素的补数（即 target - nums[i]）是否存在于数组中。这种方法的时间复杂度为 O(n)，比暴力解法的 O(n^2) 更高效。
 

function twoSum(nums, target) {
  // 创建一个哈希表来存储元素及其索引
  const numMap = new Map();

  // 遍历数组
  for (let i = 0; i < nums.length; i++) {
    // 计算当前元素的补数
    const complement = target - nums[i];

    // 检查补数是否存在于哈希表中
    if (numMap.has(complement)) {
      // 如果存在，返回补数的索引和当前元素的索引
      return [numMap.get(complement), i];
    }

    // 将当前元素及其索引存入哈希表
    numMap.set(nums[i], i);
  }

  // 如果没有找到解，抛出错误（题目保证一定有解）
  throw new Error("No two sum solution");
}

// 示例用法
console.log(twoSum([2, 7, 11, 15], 9)); // 输出: [0, 1]
console.log(twoSum([3, 2, 4], 6));      // 输出: [1, 2]
console.log(twoSum([3, 3], 6));         // 输出: [0, 1]

详细解释

1. 初始化哈希表：

   • 我们创建一个空的 Map 对象 numMap，用于存储数组中的元素及其索引。

2. 遍历数组：

   • 使用 for 循环遍历数组。
   • 对于每个元素 nums[i]，计算其补数 complement = target - nums[i]。

3. 检查补数是否存在：

   • 使用 numMap.has(complement) 检查补数是否已经存在于哈希表中。
   • 如果存在，说明我们找到了两个数，它们的和等于目标值。返回这两个数的索引。

4. 存储当前元素：

   • 如果补数不存在，将当前元素及其索引存入哈希表 numMap 中，以便后续查找。

5. 返回结果：

   • 如果找到了满足条件的两个数，函数返回它们的索引。
   • 由于题目保证每个输入都只有一个解，所以我们不需要处理找不到解的情况。不过为了完整性，我在代码中添加了一个 throw 语句。

这种方法确保我们只遍历数组一次，时间复杂度为 O(n)，空间复杂度也是 O(n)。