如何高效实现两数之和函数？求数组目标和的元素索引

最优解法：哈希表（Map）实现（时间复杂度O(n)） #

想要时间高效，哈希表是最优选择，它能在O(1)时间内完成查找操作。核心逻辑是：遍历数组时，记录已经处理过的元素及其索引，对当前元素计算需要的补数（目标和减去当前元素），如果补数已经在哈希表中，直接返回对应的两个索引。

代码实现 #

function findTwoSum(nums, target) {
  const numIndexMap = new Map();
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (numIndexMap.has(complement)) {
      return [numIndexMap.get(complement), i];
    }
    // 先检查再存入，避免同一元素被重复使用
    numIndexMap.set(nums[i], i);
  }
  return null;
}

// 测试示例
console.log(findTwoSum([3, 1, 5, 7, 5, 9], 10)); // 输出如[0,3]或[1,5]

关于Set的实现思路（不推荐，效率较低） #

Set只能存储值，无法直接关联索引，所以用Set实现需要额外步骤，且时间复杂度会退化为O(n²)：

1. 先把数组所有元素存入Set
2. 遍历数组，对每个元素计算补数，检查Set中是否存在该补数
3. 若存在，再通过indexOf找到补数的索引，确保索引与当前元素不同后返回

代码示例（仅作思路参考） #

function findTwoSumWithSet(nums, target) {
  const numSet = new Set(nums);
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (numSet.has(complement)) {
      const matchIndex = nums.indexOf(complement);
      if (matchIndex !== -1 && matchIndex !== i) {
        return [i, matchIndex];
      }
    }
  }
  return null;
}

注意：这个方法在处理重复元素时可能存在问题（比如数组中有多个相同补数时，indexOf只会返回第一个匹配项），且因为每次查找索引都要遍历数组，时间效率远不如哈希表方案。

关键细节 #

• 必须保证返回的是两个不同元素的索引，哈希表方案中先检查补数再存入当前元素，避免了同一元素被重复使用的情况（比如目标和为6，数组仅含一个3时不会错误返回[0,0]）
• 哈希表方案的空间复杂度为O(n)，这是时间换空间的典型应用，在大多数场景下都是可接受的

内容的提问来源于stack exchange，提问作者Stiven Lancheros