什么是用于此问题的最佳算法

Question

序列的平衡指数是指数,使得较低指数处的元素之和等于较高指数处的元素之和.例如,在序列A中:

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

3是均衡指数,因为:

A[0]+A[1]+A[2]=A[4]+A[5]+A[6]

6也是均衡指数,因为:

A[0]+A[1]+A[2]+A[3]+A[4]+A[5]=0

(零元素的总和为零)7不是均衡指数,因为它不是序列A的有效索引.如果你仍有疑问,这是一个精确的定义:整数k是序列的平衡指数,如果和只有当和.

假设零元素的总和等于零.写一个函数

int equi(int[] A);

给定一个序列,如果不存在均衡指数,则返回其均衡指数(任意)或-1.假设序列可能很长.

Answer 1

1. 计算所有元素的总和 A
2. 对于每个索引i,计算from A[0]中 元素A[i - 1]的总和,直到sum等于(totalSum - A[i]) / 2.

注意,来自A[0]to 的元素之和A[i - 1]可以作为运行总计被跟踪,这意味着整个算法的复杂度是O(n).实现代码留给读者练习.