如何编写优化的JavaScript findSum函数返回数组加和为指定值的两个元素

你当前实现的双层循环方案时间复杂度为O(n²)，仅适合小数据量场景，我们可以通过哈希表存储已遍历元素的方式，将时间复杂度压缩到O(n)，属于典型的空间换时间优化思路。

优化思路 #

• 遍历数组时，对每个元素计算「目标和与当前元素的差值」，该差值就是我们需要找的配对元素
• 检查差值是否已经存在于哈希表中，存在则直接返回两个配对值
• 不存在则将当前元素存入哈希表，继续遍历下一个元素

优化后代码 #

function findSum(arr, sum) {
  // 哈希表存储已遍历过的元素
  const visitedNums = new Map();
  for (const currentNum of arr) {
    const matchNum = sum - currentNum;
    // 找到匹配值直接返回结果
    if (visitedNums.has(matchNum)) {
      return { first_element: matchNum, innerElement: currentNum };
    }
    // 未找到则将当前值存入哈希表
    visitedNums.set(currentNum, true);
  }
  // 无匹配结果时返回null，可按需调整返回值
  return null;
}

性能对比 #

• 时间复杂度：O(n)，仅遍历数组1次，哈希表的查找、插入操作平均复杂度为O(1)
• 空间复杂度：O(n)，最坏情况下需要存储整个数组的所有元素，适合中大数据量场景使用

补充说明 #

你原代码中innerElement !== first_element的判断会过滤掉值相同、索引不同的合法配对（比如输入findSum([2,2],4)时，原代码会返回undefined）。如果你的需求允许使用值相同但索引不同的两个元素，上述优化后的代码已经兼容该场景；如果确实需要严格禁止值相同的元素配对，可在返回前加一层值判断即可。

内容的提问来源于stack exchange，提问作者N.SH