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

Given a sorted array and a number x, find a pair in that array whose sum is closest to x". How can we implement this with O(n) time complexity?

Example:

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

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

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

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

CodePudding user response：

The basic idea is very simple. To follow along from a very safe position, we will first try the farthest numbers.

1 2 3 4 5
^       ^
l       r

Now we have different cases. Let's be the difference between the sum of two num and the given number is d

At first we would allow any d. Set it a very large number.

Then if sum of a[l] a[r] < x then try to increase it? So it would be logical to move towards right of the sorted (ascending array) l

Else if it is a[l] a[r] > x, r-- so reduce the sum or move left.

If you are wondering why did I introduce d, maybe think a bit. But yes it is just to store the difference. So it would be absolute value of a[l] a[r]-x.

To be more precise, you only need to run it till you have l<r.

CodePudding user response：

I solved it in javascript code:

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));