如何将寻找数组中和最接近54的数对的算法从O(N²)优化到O(N)？

结论 #

无序数组无法做到严格O(N)时间复杂度求解该问题，但可以将复杂度从O(N²)优化到O(N log N)，性能提升非常明显；如果输入是已排序的数组，可以用双指针法做到O(N)时间复杂度。

已排序数组的O(N)双指针解法 #

核心逻辑是利用数组有序的特性，通过左右指针向中间移动，单次遍历就能找到最接近的数对：

• 左指针初始指向数组开头，右指针初始指向数组末尾
• 每次计算两指针指向数值的和，对比和目标值的差值，更新最优解
• 若当前和小于目标值，左指针右移获取更大的和；否则右指针左移获取更小的和
• 两指针相遇时终止遍历

完整可运行代码（适配无序数组） #

对于无序数组，先做一次排序（JS原生sort的时间复杂度为O(N log N)），再调用双指针逻辑即可，整体复杂度远低于O(N²)，适合绝大多数业务场景：

function findClosestPair(arr, target) {
  // 数组排序，复杂度O(N log N)
  const sortedArr = [...arr].sort((a, b) => a - b);
  let left = 0;
  let right = sortedArr.length - 1;
  let minDiff = Infinity;
  let bestPair = [];

  // 双指针遍历，复杂度O(N)
  while (left < right) {
    const sum = sortedArr[left] + sortedArr[right];
    const diff = Math.abs(sum - target);
    // 更新最接近的数对
    if (diff < minDiff) {
      minDiff = diff;
      bestPair = [sortedArr[left], sortedArr[right]];
    }
    // 移动指针调整当前和的大小
    sum < target ? left++ : right--;
  }
  return bestPair;
}

// 测试示例
let arr = [20 , 30, 18, 40 , 22]
const x = 54
const [num1, num2] = findClosestPair(arr, x)
console.log(`output (${num2},${num1})`) // 输出 (30,22)，和示例要求一致

补充说明 #

为什么无序数组无法做到纯O(N)复杂度？
哈希表类的方案仅适合查找「和恰好等于目标值的数对」，对于「最接近」的场景，无法快速查询到和当前值配对的最接近数值，JS原生没有支持O(1)查找相邻值的有序哈希结构，就算手动实现类似结构，插入和查询的复杂度也在O(log N)级别，整体复杂度仍为O(N log N)。

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