python - 在 python 中解决 Equi 任务

Question

来自 http://blog.codility.com/2011/03/solutions-for-task-equi.html

任务是解决均衡问题。序列的平衡索引是这样的索引，即较低索引处的元素之和等于较高索引处的元素之和。

例如，在序列A中:

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

即

A = [-7, 1, 5, 2, -4, 3, 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

当我尝试写一个 super pythonic 答案时，即:

def solution(A):
    for i in range(len(A)):
        if sum(A[:i]) == sum(A[i+1:]):
            return i 
    return -1

我得到了 O(N**2) 的最坏情况复杂度。 为什么会这样？

如何获得 O(N) 的最佳情况复杂度？

这是否给我 O(N)？ 为什么会这样？

def solution(A):
    total = sum(A)
    sum_left = 0
    for i in range(len(A)):
        sum_right = sum - sum_left
        if sum_left == sum_right:
            return i
    return -1

Answer 1

是的，您的解决方案是 O(N)，这是因为您只遍历列表一次，每次迭代都是 O(1)。您之前的解决方案也遍历了列表 1，但它对每次迭代中的所有元素求和，这也使得每次迭代都为 O(N)，导致总复杂度为 O(N^2).

但我认为您的解决方案是错误的 - 您没有累积 sum_left。您必须在循环内添加 A[i]。