尝试优化代码以删除嵌套循环或使其更高效

Question

• 我的一个朋友采用从1到n的数字序列（其中n> 0）

• 在该序列中，他选择两个数字a和b

• 他说a和b的乘积应等于序列中所有数字的和，不包括a和b

• 给定数字n，您能告诉我他从序列中排除的数字吗？

已经从Code Wars找到了该Kata的解决方案，但是当我运行它时，它在编辑器中超时（12秒后）；还有什么想法我应该如何进一步优化嵌套的for循环或删除它？

function removeNb(n) {
  var nArray = [];
  var sum = 0;
  var answersArray = [];
  for (let i = 1; i <= n; i++) {
    nArray.push(n - (n - i));
    sum += i;
  }
  var length = nArray.length;
  for (let i = Math.round(n / 2); i < length; i++) {
    for (let y = Math.round(n / 2); y < length; y++) {
      if (i != y) {
        if (i * y === sum - i - y) {
          answersArray.push([i, y]);
          break;
        }
      }
    }
  }
  return answersArray;
}

console.log(removeNb(102));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 1

我认为填充数组后没有理由计算总和，可以在填充数组的同时进行。

function removeNb(n) {
    let nArray = [];
    let sum = 0;
    for(let i = 1; i <= n; i++) {
        nArray.push(i);
        sum += i;
    }
}

而且，由于公式的输入只能有两个数字a和b a * b = sum - a - b，因此它们每个可能只有一个可能的值。因此，找到它们时无需继续循环。

if(i*y === sum - i - y) {
    answersArray.push([i,y]);
    break;
}

我建议以另一种方式查看问题。

您正在尝试使用此公式找到两个数字a和b a * b = sum - a - b。

为什么不减少这样的公式：

a * b + a = sum - b

a ( b + 1 ) = sum - b

a = (sum - b) / ( b + 1 )

然后，您只需要一个for循环即可产生b的值，请检查（sum-b）是否可被（b + 1）整除，并且除法是否会产生小于n的数字。

for(let i = 1; i <= n; i++) {
    let eq1 = sum - i;
    let eq2 = i + 1;
    if (eq1 % eq2 === 0) {
        let a = eq1 / eq2;
        if (a < n && a != i) {
            return [[a, b], [b, a]];
        }
    }
}

Answer 2

您可以使用两个指针方法在线性时间内解决此问题（本书第77页）。

为了获得对解决方案的直觉，让我们开始考虑代码的这一部分：

for(let i = Math.round(n/2); i < length; i++) {
    for(let y = Math.round(n/2); y < length; y++) {
        ...

您已经发现这是您的代码很慢的部分。您正在尝试的每一个组合i和y，但如果你没有去尝试每一个组合是什么？

让我们举一个小例子来说明为什么不必尝试每种组合。

假设n == 10我们在1 2 3 4 5 6 7 8 9 10哪里sum = 55。

假设我们尝试的第一个组合是1*10。

1*9下一步尝试有意义吗？当然不是，因为我们知道1*10 < 55-10-1我们必须增加产品，而不是减少产品。

因此，让我们尝试一下2*10。好吧，20 < 55-10-2所以我们仍然必须增加。

3*10==30 < 55-3-10==42

4*10==40 < 55-4-10==41

但是然后5*10==50 > 55-5-10==40。现在我们知道我们必须减少产品。我们可以减少5，也可以减少10，但是我们已经知道，如果减少，则没有解决方案5（因为我们在上一步中尝试过）。所以唯一的选择就是减少10。

5*9==45 > 55-5-9==41。再说一遍：我们必须减少9。

5*8==40 < 55-5-8==42。现在我们必须再次增加...

您可以将上面的示例视为具有2个指针，这些指针被初始化为序列的开头和结尾。在每一步中，我们要么

• 向左移动左指针
• 或将右指针向左移动

开始时，指针之间的区别是n-1。在每一步中，指针之间的差异减少一。我们可以在指针相互交叉时停止（并说，如果到目前为止还没有找到解决方案，那么将无法获得解决方案）。因此很明显，n在得出解决方案之前，我们不能做太多的计算。这就是说解相对于; 是线性的n。不管n增长多大，我们都不会做太多的事情n。将此与您的原始解决方案进行对比，实际上n^2，n随着解决方案的不断发展，我们最终只能进行计算。