如何将这个O(n^2)算法转换为O(n)？

Question

https://www.codewars.com/kata/is-my-friend-cheating/train/javascript

我的目标是设计一个函数，找到满足方程 a * b == sum(1, 2, 3 ..., n-2, n-1, n) - a - b 的数字对 (a, b)。下面的代码可以找到所有数字对，但速度太慢并且会超时。我在这个挑战的评论中看到算法需要具有 O(n) 复杂度才能通过。如何做到这一点？

function removeNb (n) {
  if(n===1) return null;

  let sum = (n * (n+1))/2;

  let retArr = [];
  let a = n;
  while( a !== 0){
    let b = n;
    while( b !== 0){
       if(b != a && a*b == ((sum - b) - a) ){
         retArr.push([a,b]);
       }
       b--;
    }
    a--;
  }
  retArr.sort( (a,b) => a[0] - b[0]);
  return retArr;
} 

感谢所有人的帮助！这是我的最终解决方案：

function removeNb (n) {
  let retArr = [];
  let a = 1;
  let b = 0;
  let sumN = (n * (n+1))/2; 

  while( a <= n){
    b = parseInt((sumN - a) / (a + 1));
    if( b < n && a*b == ((sumN - b) - a) ) 
      retArr.push([a,b]);
    a++;
  }
  return retArr;
} 

我认为我的主要问题是在尝试解决b时，我的代数出现了（令人尴尬的）错误。以下是适用于任何人的正确步骤：

a*b = sum(1 to n) - a - b
ab + b = sumN - a
b(a + 1) = sumN - a
b = (sumN - a) / (a + 1)

- mcavoybn

---

一个小的改进是从a开始而不是n开始。虽然这不会使它成为O(n)，但仍然有所改善。 - muratgu

这感觉像是作业... - Olian04

@Olian04 这是一道编码练习题。链接已经提供在问题的顶部。 - melpomene

Answer 1

您可以解出b的值，公式为：b = (sum - a)/(a + 1)（前提是a不等于-1）。

现在只需对a进行一次迭代即可，时间复杂度为 O(n)。

- Jochen Bedersdorfer

---

注意假阳性：3 不是 n = 5 的解决方案。 - melpomene

看起来他的代码排除了相同的一对，例如（3,3）。 - Jochen Bedersdorfer

Answer 2

let n = 100;
let sumOfNum = n => {
  return (n * (n + 1)) / 2;
};
let sum = sumOfNum(n);
let response = [];
for (let i = 1; i <= 26; i++) {
  let s = (sum - i) / (i + 1);
  if (s % 1 == 0 && s * i == sum - s - i && s <= n) {
    response.push([s, i]);
  }
}

// 这是O(N)时间复杂度

- abdullah ajibade

Answer 3

这是一个实现：

function removeNb(n){
    var sum = (1 + n) * n / 2;
    var candidates = [];

    // O(n)
    for(var y = n; y >= 1; y--){
        x = (-y + sum) / (y + 1);

        /*
         * Since there are infinite real solutions,
         * we only record the integer solutions that
         * are 1 <= x <= n.
         */
        if(x % 1 == 0 && 1 <= x && x <= n)
            // Assuming .push is O(1)
            candidates.push([x, y]);
    }

    // Output is guaranteed to be sorted because
    // y is iterated from large to small.
    return candidates;
}

console.log(removeNb(26));
console.log(removeNb(100));

https://jsfiddle.net/DerekL/anx2ox49/

从你的问题中，它也指出：

在这个序列中，他选择了两个数字a和b。

然而，它没有提到a和b是唯一的数字，因此代码中没有包含检查。

- Derek 朕會功夫

Answer 4

如其他答案所解释的那样，可以制作一个O(n)算法来解决b的问题。此外，鉴于解决方案的对称性——如果(a,b)是一个解决方案，那么(b,a)也是——也可以每次添加一对解决方案来节省一些迭代。要知道需要多少次迭代，请注意当且仅当a < -1+sqrt(1+sum)时，b>a。为了证明它：

(sum-a)/(a+1) > a ; sum-a > a^2+a ; sum > a^2+2a ; a^2+2a-sum < 0 ; a_1 < a < a_2 

a₁和a₂是二次方程解中的系数：

a_1 = -1-sqrt(1+sum) ; a_2 = -1+sqrt(1+sum)

由于a_1 < 0且a > 0，我们最终证明了当且仅当a < a_2时，b > a。

因此，在-1+sqrt(1+sum)之后，我们可以避免迭代。

一个工作示例：

function removeNb (n) {
  if(n===1) return null;
  let sum = (n * (n+1))/2;
  let retArr = [];
  for(let a=1;a<Math.round(Math.sqrt(1+sum));++a) {
      if((sum-a)%(a+1)===0) {
          let b=(sum-a)/(a+1);
          if(a!==b && b<=n) retArr.push([a,b],[b,a]);
      } 
  }
  retArr.sort( (a,b) => a[0] - b[0]);
  return retArr;
}

然而，使用这种实现仍然需要最终排序。为了避免这种情况，我们可以注意到b=(sum-a)/(a+1)是a的递减函数（通过求导证明）。因此，我们可以构建retArr连接两个数组，一个在末尾添加元素（push），一个在开头添加元素（unshift）。以下是一个可行的示例：

function removeNb (n) {
  if(n===1) return null;
  let sum = (n * (n+1))/2;
  let retArr = [];
  let retArr2 = [];
  for(let a=1;a<Math.round(Math.sqrt(1+sum));++a) {
      if((sum-a)%(a+1)===0) {
          let b=(sum-a)/(a+1);
          if(a!==b && b<=n) {
              retArr.push([a,b]);
              retArr2.unshift([b,a]); // b>a and b decreases with a
          }
      } 
  }
  retArr=retArr.concat(retArr2); // the final array is ordered in the 1st component
  return retArr;
}

作为非母语人士，我认为参考文献中的短语“所有（a，b）都是序列1到n中可能被删除的数字”意味着a！= b，因此我添加了这个约束条件。

- Franz

---

你能分享一下您是如何得出b>a，当a < -1 +sqrt(1+sum)时的吗？ - mcavoybn

啊，我明白你的意思了。将来的挑战中我得试试这个方法。非常酷，谢谢！ - mcavoybn