两数之和

问题

给定一个整数数组 nums 和一个整数 target，返回两个数的索引，使它们的和等于 target。

示例：

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

解答

方法一：哈希表（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 [];
}

复杂度分析

• 时间复杂度: O(n) - 单次遍历数组
• 空间复杂度: O(n) - 哈希表存储

关键点

• 使用哈希表存储已访问的数字
• 查找补数（target - 当前值）
• 经典面试题，掌握这个模式！