JavaScript实现Sum of Pairs函数循环配对求和结果不符预期排查

现有实现的核心问题 #

版本1问题 #

• 时间复杂度为O(n²)，面对1000万长度的测试用例必然超时
• 配对查找逻辑错误：外层遍历第一个元素的索引i，内层遍历j从0开始，找到的第一个配对是i最小的配对，而非题目要求的*整对出现最早（即配对第二个元素索引最小）*的配对，同时会重复匹配同一对的两种顺序，浪费计算资源
• 例如第一个测试用例中，i=1（值为5）时j遍历到索引5（值为5）就直接返回，但实际存在配对[3,7]的第二个元素索引为4，比5更小，才是正确结果

版本2问题 #

• 同样存在O(n²)的性能硬伤
• 逻辑硬编码不合理：仅收集3个配对就停止遍历，且判断配对优先级的jIndexCount - iIndexCount没有逻辑依据，完全无法适配所有测试场景

题目要求的「整对出现最早」，本质是找第二个元素索引最小的合法配对：只要我们从左到右遍历数组，对每个当前元素，检查能和它凑出目标和的元素是否已经出现过，第一个满足条件的配对就是正确结果，这个思路时间复杂度为O(n)，可以轻松应对千万级长度的列表。

正确实现代码 #

function sumPairs(ints, s) {
  const visited = new Set();
  for (const num of ints) {
    const complement = s - num;
    if (visited.has(complement)) {
      return [complement, num];
    }
    visited.add(num);
  }
  return undefined;
}

效果验证 #

对给出的错误测试用例：

1. 调用sumPairs([10, 5, 2, 3, 7, 5], 10)：遍历到7时检测到3已经存入集合，直接返回[3,7]，符合预期
2. 调用sumPairs([1, 2, 3, 4, 5, 8, 6, 13, 9], 10)：遍历到8时检测到2已经存入集合，直接返回[2,8]，符合预期

内容的提问来源于stack exchange，提问作者Natalia Grzywacz