算法代码优化:找到Equilibirum:在数组中查找索引,使其前缀sum等于其后缀sum

Question

这是我的任务描述:

给出了由N个整数组成的零索引数组A.

该数组的平衡指数是任何整数P,使得0≤P<N且较低指数的元素之和等于较高指数的元素之和,即A [0] + A 1 + ... + 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 solution(NSMutableArray*A); 在给定由N个整数组成的零索引数组A的情况下,返回其任何均衡指数.

如果不存在均衡指数,则该函数应返回-1.例如,给定如上所示的阵列A,该函数可以返回1,3或7,如上所述.

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

复杂性:•预期的最坏情况时间复杂度为O(N); •预期的最坏情况空间复杂度为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,则返回i.然后做一个+ = arr [i].这是O(n)操作,效率更高.