java - Codility 任务 'TapeEquilibrium' 性能

Question

我已经解决了 codility (TapeEquilibrium) 中的第一个任务。

我已设法获得 50% 的分数(正确性 100%，性能 0%)。

你能给我一些如何提高性能的提示吗？

我的结果和问题描述的链接是 here .

代码如下:

import java.util.*;

class Solution {
    public int solution(int[] A) {
        List<Integer> splittedTape = new ArrayList<Integer>();
        for (int i = 1; i < A.length; i++){
            splittedTape.add(calculateDifference(i, A));
        }
        Collections.sort(splittedTape);
        return splittedTape.get(0);
    }

    private int calculateDifference(int position, int[] array){
        int sumA = 0;
        int sumB = 0;

        for (int i = 0; i < array.length; i++){
            if (i < position){
                sumA += array[i];
            } else {
                sumB += array[i];
            }
        }
        return Math.abs(sumA - sumB);
    }
}

提前致谢。

Answer 1

我还没有完全测试极端情况，所以这可能不会产生预期的结果，但这是实现问题要求的 O(N) 解决方案。

class Solution {
public int solution(int[] A) {
    // write your code in Java SE 8
    int totalSum = 0;
    int firstSum = A[0];
    for(int i=1;i<A.length;i++)
     totalSum += A[i]; 

    int min = Math.abs(firstSum-totalSum);

    for(int i=1;i<A.length-1;i++) {
        firstSum+=A[i];
        totalSum-=A[i];
        if(Math.abs(firstSum-totalSum)<min) 
            min = Math.abs(firstSum-totalSum);

    }
    return min;
}
}