A zero-indexed array A consisting of N integers is given. An equilibrium index of this array is any integer P such that 0 <=p < N and the sum of elements of lower indices is equal to the sum of elements of higher indices, i.e. A[0] + A[1] + ... + A[P-1] = A[P+1] + ... + A[N-2] + A[N-1]. Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or P = N-1.
Write a function: int solution(int A[], int N):
that, given a zero-indexed array A consisting of N integers, returns any of its equilibrium indices(just one is enough). Return -1 if no equilibrium index exists. Assume N>=0, integer in A will not overflow.
给出一个N个元素的序号从0开始的数组，定义e-index，在这个index之前的元素之和与在这个index之后的元素之和相等。假如没有元素，按0处理。要求写出该函数，给出数组A[]和整数N，返回任意一个e-index。
1. 询问
这道题的信息已经非常充分了，基本没什么好问的。
2. 分析
直接做法
一个非常直接的做法就是，遍历每个元素，然后求其之前和之后的和，比较。这个方法有一个问题，就是求和的复杂度是O(n)。因此整体复杂度是O(n^2)。
如何改进
问题很明显在求和的方式上。因为是一个个元素遍历过去的，每次只改变一个元素，因此没有必要全部重新求和。可以维持两个和，pre和suf，代表之前和之后的元素和，每经过一个元素，pre就把该元素加入，suf就减去该元素。很明显，初始时pre=0,suf=sum(A) - A[0]。然后对于A[0]，先进行判断pre==suf，之后pre加上A[0]的值，但是suf本来就不包含A[0]，因此是要减去A[1]的值。因此pre+=A[i]，suf-=A[i+1]。然后注意边界条件，pre不能包含A[N-1]。
这样，时间复杂度降低为O(n)，空间复杂度为O(1)。
3. 代码
class Solution:
def solution(self, A, N):
if not N:
return -1
pre, suf = 0, sum(A) - A[0]
for i in range(N):
if pre == suf:
return i
if i < N - 1:
pre += A[i]
if i + 1 < N:
suf -= A[i + 1]
return -1
4. 总结
谷歌coding sample的demo问题。Easy难度。
