如何修复sumPairs函数使其返回和为指定值的首个整数对

现有代码问题分析 #

• 内层循环边界逻辑错误：j < ints.slice(i)写法不合法，slice()返回的是子数组，无法直接和数字比较大小，导致内层循环遍历范围完全不符合预期
• 数对遍历顺序错误：当前逻辑固定外层下标i，内层j从0开始遍历，会先匹配到「靠后位置的元素+靠前位置的元素」的逆序组合，所以返回了[6,4]而非顺序正确的首个匹配数对

修复方案 #

暴力遍历修复版（保持双层循环写法） #

function sumPairs(ints, s) {
  // 外层遍历第一个数的下标
  for (let i = 0; i < ints.length; i++) {
    // 内层从i的下一位开始遍历第二个数的下标，保证数对顺序和数组出现顺序一致
    for (let j = i + 1; j < ints.length; j++) {
      if (ints[i] + ints[j] === s) {
        // 找到第一个符合要求的数对直接返回，不需要额外存储判断
        return [ints[i], ints[j]];
      }
    }
  }
  // 没有匹配到返回空数组
  return [];
}

调用sumPairs([1, 2, 3, 4, 5, 6], 10)会直接返回预期结果[4,6]。

优化版（时间复杂度O(n)，适合大数组场景） #

如果数组长度较大，可使用哈希集合存储已经遍历过的数值，一次遍历就能得到结果：

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

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