两数之和

问题

给定一个整数数组 nums 和一个目标值 target，找出数组中和为目标值的两个数，返回它们的索引。

假设每个输入只有一个答案，且同一个元素不能使用两次。

示例：

输入：nums = [2, 7, 11, 15], target = 9
输出：[0, 1]
解释：nums[0] + nums[1] = 2 + 7 = 9

解答

方法一：暴力法

/**
 * 暴力法 - 两层循环遍历所有组合
 * 时间复杂度：O(n²)
 * 空间复杂度：O(1)
 */
function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
  return [];
}

// 测试
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]
console.log(twoSum([3, 2, 4], 6));      // [1, 2]

方法二：哈希表（推荐）

/**
 * 哈希表法 - 一次遍历，用 Map 存储已遍历的值
 * 时间复杂度：O(n)
 * 空间复杂度：O(n)
 */
function twoSum(nums, target) {
  // 用 Map 存储：值 -> 索引
  const map = new Map();
  
  for (let i = 0; i < nums.length; i++) {
    // 计算需要的另一个数
    const complement = target - nums[i];
    
    // 如果 Map 中存在这个数，说明找到了答案
    if (map.has(complement)) {
      return [map.get(complement), i];
    }
    
    // 将当前值和索引存入 Map
    map.set(nums[i], i);
  }
  
  return [];
}

// 测试
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]

执行过程示例

以 nums = [2, 7, 11, 15], target = 9 为例：

步骤	当前值	complement	Map 状态	结果
1	2	7	{2: 0}	继续
2	7	2	Map 中有 2	返回 [0, 1]

关键点

• 哈希表将时间复杂度从 O(n²) 降到 O(n)，用空间换时间
• 遍历时先查找再存储，避免同一元素使用两次
• complement = target - nums[i] 是关键转换思路
• Map 存储的是「值 → 索引」的映射，方便直接返回索引
• 注意处理数组中有重复元素的情况（如 [3, 3]）