javascript - 在 O(n) 内获取两个数组之间所有可能的乘法值？

Question

在从 (n>0) 开始的数字序列中，我需要找到两个数字，当它们彼此相乘时，返回的值与序列总和减去这些数字的总和相同(sum - (x+y ))。我已经编写了一个程序，但我认为效率不够。有没有一种方法可以在不嵌套循环的情况下获得相同的结果？这是我的代码:

function removeNb (n) {

result = [];
var sum = (n*(n+1))/2

for(var x=n; x > 0; x--){
  for(var y = 1; y<=x; y++){

  z= x*y;
  var r = sum-(y+x);

  if(z == r){
  result.push([y,x],[x,y])} *//because with inverted loops (y++, x--) only unique values are left.*
  }
 return result;
} 

Answer 1

到目前为止，您的解决方案的复杂度为 O(n^2)。据我所知，该序列不是随机的。它是序列 1, 2, 3 ... N。我假设从下面的行 sum = (n*(n+1))/2。

现在让我们看一下方程 r = z，它实际上是 x*y = sum - x - y。您可以创建一个循环，将 x 从 1 迭代到 n 并计算 y。 Y =(总和 - x)/(x +1)。如果 y 等于或小于 N，则有一个解 (x,y)。使用这种方法，您将创建一个循环，复杂度将为 O(n)。

您还可以预先计算值并将其存储为数组。如果 n 在某个小范围内，此解决方案很有用。