No.0006-CareerCup

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难度。