javascript - JavaScript Codility演示解决方案

昨晚我正在看关于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上找到它。

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

非常感谢！

最佳答案

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

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

您只需要在数组上循环两次：一次获得元素的总和，一次找到平衡。在第二个循环开始时，左边的总和== 0，右边的总和== total。遍历元素，您只需要更新总和：右总和=总-左总和-当前索引处的值，然后比较right == left和否-左总和以当前索引处的值增长。

我已经为这个得分了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;
}

关于javascript - JavaScript Codility演示解决方案，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17164164/