问题：
给出了一个由N个整数组成的非空零索引数组A。
数组A代表磁带上的数字。任何整数P，例如
0 < P < N，将此磁带分为两个非空部分：
A[0], A[1], ..., A[P − 1] and A[P], A[P + 1], ..., A[N − 1].
这两个部分之间的差是：
|(A[0] + A[1] + ... + A[P − 1]) − (A[P] + A[P + 1] + ... + A[N − 1])|
换句话说，它是第一部分之和与第二部分之和之间的绝对差
。对于
例如，考虑数组A，这样：
A[0] = 3
A[1] = 1
A[2] = 2
A[3] = 4
A[4] = 3
我们可以将此磁带分成四个位置：
P = 1, difference = |3 − 10| = 7
P = 2, difference = |4 − 9| = 5
P = 3, difference = |6 − 7| = 1
P = 4, difference = |10 − 3| = 7
>编写一个函数：
int solution(int A[], int N);，给定一个由N个整数组成的非空零索引数组A，它返回可以实现的最小
差。
这就是我的实现方式。我得到了50％的复杂度N * N。如何使它更清洁？
// you can also use imports, for example:
import java.math.*;
import java.util.*;
import java.lang.*;
class Solution {
public int solution(int[] A) {
// write your code in Java SE 7
int sizeOfArray = A.length;
int smallest = Integer.MAX_VALUE;
int result = 0;
for(int i=1;i<sizeOfArray;i++){
int difference = Math.abs(sumOfArray(subArray(0,i,A))-
sumOfArray(subArray(i,sizeOfArray,A)));
//System.out.println("difference"+difference);
result = Math.min(smallest,difference);
smallest = result;
}
return result;
}
public int sumOfArray(int[] arr) {
int sum=0;
for(int i:arr) {
sum += i;
}
return sum;
}
public int[] subArray(int begin, int end, int[] array) {
return Arrays.copyOfRange(array, begin, end);
}
}
#1 楼
命名参数的Java命名约定为camelCase。您应该在此处将此参数重命名为
A：public int solution(int[] A)
最好使其看起来像以下代码，或者使用更好的代码满足您需求的名称：
public int solution(int[] arrayA)
对于
arr我没有针对名为int []的变量，但是您在不同的方法中使用arr和array 。我建议您使用一个名称，或者如果它们表示不同的意思，则尝试使用较少的通用名称。格式化
您的格式设置总体来说非常好，重新一致。有时候，您可以使用一些空格。
for(int i=1;i<sizeOfArray;i++)
您可以添加一些空格以清楚地定义三个部分for循环的说明：
for(int i=1; i<sizeOfArray; i++)
我不会评估您的算法，因为这不是我的专长。
#2 楼
您应该能够在\ $ O（n）\ $时间和\ $ O（1）\ $空间中完成此操作。保持左和右的总和。在测试每个\ $ p \ $时，请从一侧扣除一个数字，然后再记入另一侧。public static int minDiff(int[] a) {
int leftSum = 0, rightSum = 0;
for (int ai : a) {
leftSum += ai;
}
int minDiff = Integer.MAX_VALUE;
for (int p = a.length - 1; p >= 0; p--) {
rightSum += a[p];
leftSum -= a[p];
int diff = Math.abs(leftSum - rightSum);
if (diff == 0) {
return 0;
} else if (diff < minDiff) {
minDiff = diff;
}
}
return minDiff;
}
评论
\ $ \ begingroup \ $
基本上，与@konijn的解决方案相同。
\ $ \ endgroup \ $
– 200_success
14年3月14日在18:31
\ $ \ begingroup \ $
当输入包含负值时，此解决方案将不起作用...两侧的和不会增加
\ $ \ endgroup \ $
–rolfl
14年3月14日在18:31
\ $ \ begingroup \ $
@rolfl您能提供一个反例吗？
\ $ \ endgroup \ $
– 200_success
2014年3月14日18:32
\ $ \ begingroup \ $
没关系，我误解了您的描述和实施。您的描述说“保留剩余的总和”，但这不是您的代码所做的，您的代码将计算所有值的总和，然后减去所有值。
\ $ \ endgroup \ $
–rolfl
14年3月14日在18:37
\ $ \ begingroup \ $
除了我的上一个Java代码在1.4中，所以我写了一些JavaScript;）
\ $ \ endgroup \ $
– konijn
2014年3月14日在18:39
#3 楼
从头开始，您似乎多次调用
sumofArray，您只需要调用一次即可。从一开始，您就为它调用一次整个数组的结果应该是
13 然后对于位置0（值3），减去
3，得到3和10（13-10）然后对于位置1（值1）。将
1添加到3，然后从1中减去10，得到4和9 ，然后将位置2（值2）添加到
2中，然后从4中减去2，得到9和6等。。
这样，如果我计数正确，您可以两次访问所有元素。
我在评论中提到，我将重命名为
7-> arr 我不是Java专家，但是JavaScript足够接近，您应该可以使用：
var A = [3,1,2,4,3];
function sumArray( array )
{
var sum = 0, index = array.length;
while(index--)
sum += array[index];
return sum;
}
function tapeEquilibrium( array )
{
var left = sumArray( array ),
right = 0,
smallest = left,
index = array.length,
difference;
while( index-- )
{
right += array[index];
left -= array[index];
difference = Math.abs( right-left );
if( difference < smallest )
smallest = difference;
}
return smallest;
}
console.log( tapeEquilibrium( A ) );
附加的优点是很少有额外的内存需要检查非常大的阵列时需要。
#4 楼
解决这个问题的技巧就在于算法。如果您以“明智”的方式处理数据，则可以使用\ O（n）\ $复杂度的解决方案。请考虑以下算法：创建一个相同大小的新数组，将其命名为
sum 在
sum数组中填充左侧所有值的总和在原始数据数组中，一旦
sum数组被完全填充，您就会知道该数组的总和。这使您可以确定平衡点总和是多少，总数的一半。
您可能会倾向于只对求和数组进行二进制搜索以找到占总数一半的位置，但是如果输入数组中存在负值，这将失败。
唯一的解决方案是扫描总和以寻找值的一半，如果找到精确的一半，则短路。
public static final int tapeEquilibrium(int[] data) {
if (data.length < 3) {
// rules indicate 0 < P < N which implies at least 3-size array
throw new IllegalStateException("Need minimum 3-size array input");
}
int[] sums = new int[data.length];
for (int i = 1; i < sums.length; i++) {
sums[i] = sums[i - 1] + data[i - 1];
}
int total = sums[sums.length - 1] + data[data.length - 1];
int min = Integer.MAX_VALUE;
for (int i = 0; i < sums.length; i++) {
int diff = Math.abs((total - sums[i]) - sums[i]);
if (diff == 0) {
return 0;
}
if (diff < min) {
min = diff;
}
}
return min;
}
#5 楼
关于前面未提到的原始代码，只需添加一点便笺：该代码仅使用
subArray进行总结：int difference = Math.abs(sumOfArray(subArray(0,i,A))-
sumOfArray(subArray(i,sizeOfArray,A)));
使用原始数组会更快：
public int sumOfArray(int[] array, int begin, int end) {
int sum = 0;
for (int i = begin; i < end; i++) {
sum += array[i];
}
return sum;
}
int difference = Math.abs(sumOfArray(subArray(0,i,A))-
sumOfArray(subArray(i,sizeOfArray,A)));
这使代码更易于阅读（和维护）。
评论
\ $ \ begingroup \ $
我会去数组
\ $ \ endgroup \ $
– konijn
14年3月14日在17:51