Google面试题hasPairsWithSum：如何返回和为目标值的数对索引且时间复杂度低于O(n²)

你原有实现的时间复杂度为O(n²)：外层for循环遍历数组耗时O(n)，内层array.find也需要遍历数组耗时O(n)，嵌套后整体复杂度为O(n²)，不符合性能要求。我们可以采用哈希表存储已遍历元素与对应索引的方案优化，整体时间复杂度可降到O(n)，仅需一次数组遍历即可得到结果。

function hasPairsWithSum(array, sum) {
  // 边界判断：数组长度不足2不可能存在符合要求的数对
  if (array.length < 2) return null;
  // 哈希表存储已遍历元素：key为元素值，value为对应索引
  const numMap = new Map();
  for (let i = 0; i < array.length; i++) {
    const currentNum = array[i];
    // 计算当前元素的补数：目标和减去当前值就是需要匹配的另一个数
    const complement = sum - currentNum;
    // 补数已在哈希表中存在，直接返回两个数的索引
    if (numMap.has(complement)) {
      return [numMap.get(complement), i];
    }
    // 补数不存在则把当前元素和索引存入哈希表，供后续遍历判断
    numMap.set(currentNum, i);
  }
  // 遍历完成未找到符合条件的数对返回null
  return null;
}

console.log(hasPairsWithSum([1,2,4,4],8)); // 输出结果：[2, 3]

• 时间复杂度：仅遍历数组1次，Map的查询、写入操作都是O(1)，整体复杂度为O(n)，满足小于O(n²)的要求
• 返回规则：存在符合条件的数对时，返回[第一个数的索引, 第二个数的索引]的数组；不存在符合条件的数对、或数组长度不足2时返回null，你也可以根据业务需求调整为返回空数组等其他值
• 兼容性：ES6及以上环境支持Map，如果需要兼容更低版本JS环境，也可以把Map替换为普通对象实现相同逻辑

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