TapeEquilibrium，两个边缘案例失败的解决方案

Question

目前正在研究codility的问题以供练习，由于某种原因我无法获得超过83%的整体正确率，最初我以100%的正确率解决了它但时间复杂度为N^2（它需要为 N 或更低）

我已经调整了我的代码以能够在 O(N) 内解决，但现在我的正确性下降到 77%，我目前正在尝试解决 2 个元素的情况 ie) [1000,-1000] 应该 return 2000，但是我 return a 0;

Link 至关于可亲性的问题：https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/

问题：

给出一个由N个整数组成的非空数组A。数组 A 表示磁带上的数字。

任何整数 P，使得 0 < P < N，将此磁带分成两个非空部分：A[0]、A[1]、...、A[P − 1] 和 A[ P], A[P + 1], ..., A[N − 1].

两部分的差值为：|(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|

换句话说，就是第一部分的总和与第二部分的总和之差的绝对值

为以下假设编写一个有效的算法：

N为[2..100,000]范围内的整数；数组 A 的每个元素都是 [−1,000..1,000]

范围内的整数

class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
        int pval = Integer.MAX_VALUE;
        int sum = 0;
        int pone = 0;
        int ptwo = 0;
        int currdiff = 0;
        for(int i = 0; i<A.length; i++ ){
            sum += A[i];
        }
        
        ptwo = sum;
        for(int j = 0; j< A.length; j++){
            pone += A[j];
            ptwo -= A[j];
            currdiff = Math.abs(ptwo - pone);
            if(currdiff < pval)
                pval = currdiff;
        }
        return pval;
    }
}

Answer 1

Any integer P, such that 0 < P < N, splits this tape into two non-empty parts

这里的“非空”很关键。如果您尝试在第二个循环中打印两个部分，您会发现在最后一次迭代中第二部分是空的。

您需要做的就是跳过循环中的最后一次迭代：

public int solution(int[] A) {
    int pval = Integer.MAX_VALUE;
    int sum = 0;
    int pone = 0;
    int ptwo = 0;
    int currdiff = 0;
    for(int i = 0; i<A.length; i++ ){
        sum += A[i];
    }
    
    ptwo = sum;
    for(int j = 0; j< A.length-1; j++){ //<- notice -1 here
        pone += A[j];
        ptwo -= A[j];
        currdiff = Math.abs(ptwo - pone);
        if(currdiff < pval)
            pval = currdiff;
    }
    return pval;
}

TapeEquilibrium，两个边缘案例失败的解决方案

TapeEquilibrium, Solution Failing Two Edge Cases

java

time-complexity