javascript - 如何优化此 javascript 函数以提高速度？

Question

我刚刚参加了 Codility 磁带平衡测试 here

正如您从我的分数中看到的那样，我对函数执行的速度不够好。任何人都可以给我一些指示，以便我可以优化此代码并接近 100% 吗？

这是代码...

function solution(A) {

    var minimumAbsDiff = null;

    for(var currentIndex =1;currentIndex < A.length;currentIndex ++){
        var bottomHalf = getTotal(0,currentIndex-1,A);
        var topHalf = getTotal(currentIndex,A.length-1,A);

         var absDiff = Math.abs(bottomHalf - topHalf);
         if(minimumAbsDiff == null){
            minimumAbsDiff = absDiff;
         }else{
            if(absDiff < minimumAbsDiff) minimumAbsDiff = absDiff;
         } 
    }

    return minimumAbsDiff;
}

function getTotal(start,end,arrayTocheck){
    var total = 0;
    for(var currentIndex = start;currentIndex <= end;currentIndex++){
        total = total + arrayTocheck[currentIndex];
    }
    return total;
}

Answer 1

您不想优化速度。你想降低 algorithmic complexity .您当前的算法是 O(n²)，而任务说明明确指出

• expected worst-case time complexity is O(N);
• expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).

那么使这成为可能的洞察力是什么？对于 P，每个总差异与其他差异只有很小的距离。如果比较 |(A[0] + ... + A[P-1]) - (A[P] + ... + A[N-1])| 的值P 和 P+1，要做的工作量只有一个常数。

function solution(A) {
     var left = 0,
         right = A.reduce(function(a, b) { return a + b; }, 0);
     var min = Infinity;
     for (var p = 0; p<A.length-1; p++) {
         left += A[p];
         right -= A[p];
         min = Math.min(min, Math.abs(left - right));
     }
     return min;
}