我的 Codility 磁带平衡解决方案性能有什么问题

Question

这是我未通过性能要求的解决方案。据我所知，它与我查找过的其他解决方案类似：

function solution(A) {
    let slice = A.slice(1,A.length);
    let firstSliceSum = A[0];
    let lastSliceSum = slice.reduce((a, b) => a + b);
    let smallestValue = Math.abs(firstSliceSum-lastSliceSum);
    for(let i=1;i<A.length-1;i++){
        let shift = slice.shift();
        firstSliceSum=firstSliceSum+shift;
        lastSliceSum=lastSliceSum-shift;
        let diff = Math.abs(firstSliceSum-lastSliceSum);
        if(diff<smallestValue)smallestValue=diff;
    }
    return smallestValue;
}

它只有一个迭代元素的 for 循环，不包括初始的 "reduce" 函数。我见过类似的 Java 应该 100% 通过的解决方案。 Link 来挑战：https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/

Answer 1

这里有几个问题。

如前所述，您在循环 which has a time complexity of O(n) 中使用了 shift()。最终使您的代码 O(n²).
其次，您也在考虑第一个索引 0 总和，而提到的约束表示任何 0 < P < N.

引用那里提到的问题陈述：

Any integer P, such that 0 < P < N, splits this tape into two non-empty parts: A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].

所以你必须计算从 1 到 A.length-1。

片段：

function solution(A) {
  let slice = A.slice(1, A.length);
  let firstSliceSum = A[0];
  let lastSliceSum = slice.reduce((a, b) => a + b);
  let smallestValue = -1;
  for (let i = 1; i < A.length; i++) {
    let diff = Math.abs(firstSliceSum - lastSliceSum);
    if (smallestValue == -1 || diff < smallestValue) smallestValue = diff;
    firstSliceSum += A[i];
    lastSliceSum -= A[i];
  }
  return smallestValue;
}

console.log(solution([3, 1, 2, 4, 3]));

在上面（正确的代码）中，我们将 smallestValue 初始化为 -1 因为绝对值不能为负。
在循环中，我们避免了.shift()，只取firstSliceSum和lastSliceSum的差值。
稍后，我们从 lastSliceSum 减少 A[i] 并将其添加到 firstSliceSum，因为我们需要为下一次即将到来的拆分考虑 A[i] 并将其从右边部分移除分裂。

我的 Codility 磁带平衡解决方案性能有什么问题

What is wrong with my Tape-Equilibrium solutions performance for Codility

javascript

puzzle

algorithm