算法代码优化：找到平衡点：在数组中找到一个索引，使其前缀和等于其后缀和

Question

这是我的任务描述：

A zero-indexed 给定一个由N个整数组成的数组A。

这个数组的平衡索引是任何整数 P 使得 0 ≤ P < N 并且较低索引元素的总和等于较高索引元素的总和，即 A[0] + A1 + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1].

假定零元素之和等于 0。如果 P = 0 或 P = N−1，则可能发生这种情况。例如，考虑以下由 N = 8 个元素组成的数组 A：

A[0] = -1
A[1] =  3
A[2] = -4
A[3] =  5
A[4] =  1
A[5] = -6
A[6] =  2
A[7] =  1

P = 1 is an equilibrium index of this array, because:
•   A[0] = −1 = A[2] + A[3] + A[4] + A[5] + A[6] + A[7]
P = 3 is an equilibrium index of this array, because:
•   A[0] + A[1] + A[2] = −2 = A[4] + A[5] + A[6] + A[7]
P = 7 is also an equilibrium index, because:
•   A[0] + A[1] + A[2] + A[3] + A[4] + A[5] + A[6] = 0

并且没有索引大于 7 的元素。 P = 8 不是均衡指数，因为它不满足条件 0 ≤ P < N.

写一个函数： int 解决方案（NSMutableArray *A）；即，给定一个由 N 个整数组成的 zero-indexed 数组 A，returns 它的任何平衡指数。

如果不存在均衡指标，函数应该return −1。例如，给定上面显示的数组 A，函数可能 return 1、3 或 7，如上所述。

假设： • N 是[0..100,000] 范围内的整数； • 数组A的每个元素都是[−2,147,483,648..2,147,483,647].

范围内的整数

复杂性： • 预计worst-case 时间复杂度为O(N)； • 预期 worst-case space 复杂度为 O(N)，超出输入存储（不计算输入参数所需的存储）。

可以修改输入数组的元素。

这是我对 Objective C 中问题的解决方案：

-(int)solution:(NSArray *) A{
for (int i=0; i<A.count; i++) {

    NSUInteger backwardsTotal = 0;
    if (i > 0) {
        for (int k=0; k<i; k++) {
            NSNumber *kValue = A[k];
            backwardsTotal += kValue.intValue;
        }
    }

    NSUInteger forwardTotal = 0;
    for (int j=i+1; j<A.count; j++) {
        NSNumber *jValue = A[j];
        forwardTotal += jValue.intValue;
    }

    if (backwardsTotal == forwardTotal) {
        return i;
    }
}

return -1;
}

我该如何优化这个解决方案？

根据@Nikki 评论对方法所做的更改：

-(int)solution:(NSArray *) A{
NSUInteger a = 0, b = 0;

for (int i=0; i<A.count; i++) {
    NSNumber *iValue = A[i];
    b += iValue.intValue;
}
NSLog(@"Total: b: %ld", b);

for (int k=0; k<A.count; k++) {
    NSNumber *kValue = A[k];
    b -= kValue.intValue;

    NSLog(@"b: %ld", b);
    NSLog(@"a: %ld", a);

    if (a == b)
        return k;

    a += kValue.intValue;

}

return -1;
}

我正在测试上面的代码如下：

//    NSArray *array = @[@"-3", @"0", @"3"];
NSArray *array = @[@"-2", @"4", @"-5", @"6", @"1", @"-6", @"2", @"1"];
NSUInteger one = [self solution:array];
NSLog(@"one: %ld", one);//returns 7

该解决方案似乎效果更好。但是，它仍然不是完美的，并且使用 O(N**2) 时间复杂度。并且在其他性能测试中也存在超时错误。

以下截图：

这还能优化吗？

Answer 1

您当前的解决方案是 O(n^2) 次操作（您对整个数组求和 n 次）。

你可以在任何时候只有 2 个变量，a 和 b，将 a 设置为零，将 b 设置为数组的总和。然后，遍历所有索引。当遍历索引 i 时，首先执行 b -= arr[i]。然后，如果 a==b，returni。然后做一个+= arr[i]。即O(n)次运算，效率更高

Answer 2

这个怎么样，希望对你有用..

int equi(int arr[], int n) {
if (n==0) return -1; 
long long sum = 0;
int i; 
for(i=0;i<n;i++) sum+=(long long) arr[i]; 

long long sum_left = 0;    
for(i=0;i<n;i++) {
    long long sum_right = sum - sum_left - (long long) arr[i];
    if (sum_left == sum_right) return i;
    sum_left += (long long) arr[i];
} 
return -1; 
}

Answer 3

来自 Codility 的官方 C 解决方案

http://blog.codility.com/2011/03/solutions-for-task-equi.html

int equi(int arr[], int n) {
    if (n==0) return -1; 
    long long sum = 0;
    int i; 
    for(i=0;i<n;i++) sum+=(long long) arr[i]; 

    long long sum_left = 0;    
    for(i=0;i<n;i++) {
        long long sum_right = sum - sum_left - (long long) arr[i];
        if (sum_left == sum_right) return i;
        sum_left += (long long) arr[i];
    } 
    return -1; 
}

注意两点：

long long用于防止溢出。这已经足够了，因为在 + 中提到的最小尺寸保证以及 Codility 的输入
处理 n==0 特殊情况

其他语言：

Java
C#faster implementation of sum ( for Codility test )
Python Index in an array such that its prefix sum equals its suffix sum - best solution

算法代码优化：找到平衡点：在数组中找到一个索引，使其前缀和等于其后缀和

Algorithm Code Optimization: Find the Equilibirum: Find an index in an array such that its prefix sum equals its suffix sum

arrays

algorithm

optimization

objective-c

compiler-optimization