在 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

当我尝试写一个超级 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]。

Answer 2

重写为生成器函数，

def solution(a):
    sum_left, sum_right = 0, sum(a)
    for index,value in enumerate(a):
        sum_right -= value
        if sum_left == sum_right:
            yield index
        sum_left += value

然后求所有解，

list(solution([-7, 1, 5, 2, -4, 3, 0]))    # => [3, 6]

Answer 3

只是为了稍微调整 Hugh 的答案，练习要求您 return 平衡指数之一（如果 none 找到，则为 -1），而不是生成器，因此通过的解决方案看起来像:

def solution(A):
    sum_left, sum_right = 0, sum(A)
    for index, value in enumerate(A):
        sum_right -= value
        if sum_left == sum_right:
            return index
        sum_left += value
    return -1

在 python 中解决 Equi 任务

Solving Equi task in python

python

math

complexity-theory

list