磁带平衡 Codility 培训计划

Question

我提交了 Codility 中磁带均衡问题的解决方案。[Codility培训][1]

问题描述如下：

给出了一个由 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])| 换句话说，它是第一部分的总和与第二部分的总和之间的绝对差。

我提交的解决方案是：

class Solution {
  public int solution(int[] A) {

    long d = A[0] - A[A.length-1];
    int l = 1;
    int r = A.length -2;

    while(l <= r) {
      if (Math.abs(d + A[l]) < Math.abs(d - A[r])) {
        d += A[l];
        l++;
      }
      else {
        d -= A[r];
        r--;
      }
    }
    return (int) Math.abs(d);
  }
}

我达到了 85% 的准确率，但无法纠正某些用例。有人可以帮我找出这个解决方案的问题所在。谢谢

Answer 1

以下是我的 100% 解决方案：

class Solution {
public int solution(int[] A) {
    // write your code in Java SE 8
    // int idx = 0;
    int sumPre = A[0];
    int sumPost = 0;
    for (int i = 1; i < A.length; i++) {
        sumPost += A[i];
    }
    int difMin = Math.abs(sumPost - sumPre);
    int tempSub = 0;
    for (int i = 1; i < A.length - 1; i++) {
        sumPre += A[i];
        sumPost -= A[i];
        tempSub = Math.abs(sumPost - sumPre);
        if (tempSub < difMin) {
            difMin = tempSub;
            // idx = i+1;

        }
    }
    return difMin;
}
}

我找不到他们的测试输入，但我发现一个奇怪的事情是，当“for(int i = 1; i < A.length - 1; i++)”更改为“ for(int i = 1; i < A .length; i++)”，那么它会触发两次错误运行......所以它仍然必须是边界值问题。如果有人发现测试输入可以破坏有效性，请与我们分享，谢谢。

注意：{1,-1} 确实触发了这个问题，因为 P < N，所以至少应该在右边留下一个元素。-> {1,-1},{} 根据问题定义不是有效的解决方案。问题解决了。