Codility Tape Equilibrium in Python

发表于 更新于 分类于 ， Disqus：

算法复杂度分析

情况 时间复杂度 空间复杂度
最优 O(N) O(1)
平均 O(N) O(1)
最差 O(N) O(1)

算法分析

构造数组前段总和first = A[0]以及数组后端总和last = sum(A) - A[0]，第一个差值便是abs(first - last)。遍历数组时，不必每次都重新构造数组前段总和以及数组后端总和，只需向first增加当前遍历元素，想las减去当前遍历元素，另外，也只要一个变量min_diff来记录最小差值即可。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
def solution(A):
    # write your code in Python 2.7
    first = A[0]
    last = sum(A) - A[0]
    N = len(A)
    min_diff = abs(first - last)
    for i in xrange(1, N - 1):
        num = A[i]
        first += num
        last -= num
        min_diff = min(abs(first - last), min_diff)
    return min_diff