JavaScript Codility 演示解决方案

Question

昨晚我在 Codility 上查看了 Equi 演示任务，并为以下功能获得了 12/100 分:

function solution(A) {
    var n = A.length;
    var p = 0;
    var sum = 0;
    var sumLeft = 0;
    var sumRight = 0;
    var equilExists = 0;

    if (n == 0) {
        return -1;
    }

    for (i=0; i<=n; i++) {
        sum = A[i];
        for (j=0; j<=n; j++) {
        if (j < i) {
            sumLeft += A[j];
        } else if (j > i) {
            sumRight += A[j];
        }
        if (sumLeft == sumRight) {
            equilExists = 1;
            p = i;
            return p;
                }
        }
    }

    if (equilExists == 0) {
        return -1;
    }
}

对于那些不熟悉该任务的人，可以在 http://blog.codility.com/2011/03/solutions-for-task-equi.html 找到它。

我想知道是否有人可以帮忙指出我的解决方案失败的地方？

非常感谢!

Answer 1

您的解决方案最大的问题是嵌套循环。

您在每个索引处迭代整个数组，以计算当前索引处左右部分的总和。他们的要求之一是 O(n) 复杂度，而你的要求是 O(n^2) (我认为)。

您只需循环数组两次:一次获得元素之和，一次找到平衡点。在第二个循环开始时，左侧的总和 == 0，右侧的总和 == 总计。迭代元素，您只需要更新总和:右总和 = 总和 - 左总和 - 当前索引处的值，然后比较是否右 == 左，如果不是 - 左总和按当前索引处的值增长。

我为此获得了 100 分:

function solution(A) {
  var total = (function(a){ var l = a.length, s = 0; while(--l>-1){ s+=a[l] } return s; }(A)), 
  eq = -1, 
  l = A.length, 
  Lsum = 0, 
  Rsum = 0; 
  A.forEach(function(n,i){ 
    Rsum = total - Lsum - n; 
    if(Rsum == Lsum){ eq = i; /* in fact no need to continue, should terminate here. */ } 
    Lsum += n; 
  }); 
  return eq;
}