我的磁带均衡解决方案的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％通过。链接到挑战：https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/

Answer 1

我可以看到您的代码有2个主要的性能问题：

1]您正在使用slice()复制数组，并使用shift()更改数组。考虑到有更简单的解决方案根本不使用这些数组函数，因此它们是（相对）昂贵的操作。

2）不必遍历整个数组以确保您拥有最小的整数。在for循环的每次迭代中，您都在计算磁带的“左”和“右”片的差异。您应该存储上一次迭代的差异并将其与当前迭代的差异进行比较。 如果当前差异大于上一个迭代的差异，则可以确定前一个差异是最小的整数，并且可以尽早退出循环。

这里的解决方案应该更有效：

function solution(A) {
  let sum = A.reduce((a,b) => a+b);
  let leftSide = 0;
  let rightSide = sum;
  let diff, prevDiff;
  let result;
  for (var i = 0; i < A.length; i++) {
    prevDiff = diff;
    leftSide = leftSide + A[i];
    rightSide = rightSide - A[i];
    diff = Math.abs(leftSide-rightSide);
    if (diff > prevDiff) {
      result = prevDiff;
      break;
    }
  }
  return result;
}