如何在时间复杂度为 O(n) 的数组中找到和最接近 x 的一对数字？

Question

给定一个 sorted array 和一个数字 x，在该数组中找到其和最接近 x 的一对。我们如何用 O(n) 时间复杂度来实现它？

示例：

fn([10,22,28,29,30,40], 54)  // => [22, 30]

fn([1,3,4,7,10], 15)  // => [4, 10]

fn([5], 7)  // => []

fn([], 7)  // => []

更新：

这是我解决这个问题的最新尝试，但没有用，而且时间复杂度为 O(n^2)。

function fn(arr, x) {
  let res = [];
  if (arr.length < 2) return res;

  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = arr.length - 1; j > i; j--) {
      let t = Math.abs(arr[i] + arr[j] - x);
      if (arr[i] + arr[j] === x) return (res = [arr[i], arr[j]]);
      if (arr[i] + arr[j] > x) {
        if (t > Math.abs(arr[i] + arr[j] - x)) {
          t = Math.abs(arr[i] + arr[j] - x);
          res = [arr[i], arr[j]];
        }
      }
    }
  }
  return res;
}

console.log(fn([10, 22, 28, 29, 30, 40], 54));
console.log(fn([1, 3, 4, 7, 10], 15));

Answer 1

基本思路很简单。为了从一个非常安全的位置跟进，我们会先尝试最远的数字。

1 2 3 4 5
^       ^
l       r

现在我们有不同的情况。设两个num之和与给定数之差为d

起初我们允许任何 d。设置一个非常大的数字。

那么如果 a[l]+a[r] < x 的总和那么尝试增加它？因此，向排序（升序数组）的右侧移动是合乎逻辑的 l++

否则如果是 a[l]+a[r] > x，r-- 所以减少总和或向左移动。

如果你想知道我为什么要介绍d，也许想一想。但是，是的，它只是为了存储差异。所以它将是绝对值 a[l]+a[r]-x.

更准确地说，你只需要运行它直到你有l<r。

Answer 2

我用javascript代码解决了：

function fn(arr, x) {
  let res = [];
  if (arr.length < 2) return res;

  let i = 0,
    j = arr.length - 1,
    t = Math.abs(arr[i] + arr[j] - x);
    
  while (i < j) {
    let s = arr[i] + arr[j];
    
    if (s === t) {
      res = [arr[i], arr[j]];
      break;
    }
    
    if (s < x) {
      i++;
      if (Math.abs(arr[i] + arr[j] - x) < t) {
        t = Math.abs(arr[i] + arr[j] - x);
        res = [arr[i], arr[j]];
      }
    }
    
    if (s > x) {
      j--;
      if (Math.abs(arr[i] + arr[j] - x) < t) {
        t = Math.abs(arr[i] + arr[j] - x);
        res = [arr[i], arr[j]];
      }
    }
    
  }
  
  return res;
}

console.log(fn([10, 22, 28, 29, 30, 40], 54));
console.log(fn([1, 3, 4, 7, 10], 15));
console.log(fn([5], 7));
console.log(fn([], 7));

如何在时间复杂度为 O(n) 的数组中找到和最接近 x 的一对数字？

How to find a pair of numbers in the array which sum is closest to x with O(n) time complexity?

javascript

algorithm

time-complexity