降低列表操作的复杂性

Question

我有一个python问题需要解决,但是我得到了一些关于解决方案性能不佳的评论......所以我想在这里分享它,并检查可能的改进:

问题很简单,就是要找到列表第一部分之和与第二部分之和之间的最小绝对差.

作为一个例子,如果我们有:

L = [3, 1, 2, 4, 3]

我们可以将其分为四个阶段:

i = 1, abs difference = |3 ? 10| = 7 
i = 2, abs difference = |4 ? 9| = 5 
i = 3, abs difference = |6 ? 7| = 1 
i = 4, abs difference = |10 ? 3| = 7 

在此示例中,脚本应1作为最小绝对差值返回.

正如我所说,对我来说这很容易,我做了:

def get_minAbsDiff(L):
    return min([abs(sum(L[0:i+1]) - sum(L[i+1:])) for i in xrange(len(L)-1)])

但是,似乎这是太时间复杂的解决方案O(N*N)

是否有可能为这个问题得到O(N)？

编辑:

是其他人告诉我这个O(N*N)的复杂性,我实际上并不知道这个例子是否属实.

Answer 1

实现O(N)解决方案的关键是要认识到,当您在列表中移动时,您将减去一个总和并添加到另一个总和.所以...

def get_minAbsDiff(L):
    leftSum = 0
    rightSum = sum(L)
    minDiff = rightSum

    for i in L:
        leftSum += i
        rightSum -= i
        diff = abs(leftSum-rightSum)

        if diff < minDiff: minDiff = diff

    return minDiff