algorithm - 给定序列的平衡索引 : What is the best algorithm to find one?

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，计算从A[0]到A[i - 1]的元素之和，直到总和等于 (totalSum - A[i])/2。

请注意，从 A[0] 到 A[i - 1] 的元素总和可以作为运行总计进行跟踪，这意味着整个算法是 O(n)。作为代码实现留给读者作为练习。