python - 数组中的索引，使其前缀和等于其后缀和 - 最佳解决方案

Question

问题

给出了一个由 N 个整数组成的零索引数组 A。该数组的平衡索引是满足 0 ≤ P < N 的任意整数 P低指标元素之和等于高指标元素之和。

A[0] + A[1] + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1].

假定零元素之和等于 0。如果 P = 0 会发生这种情况或者如果 P = N−1 .

N 的范围:[0 ... 100,000] .

元素范围:[−2,147,483,648 ... 2,147,483,647] .

复杂性:最坏情况时间 O(N)

我的 5 分钟解决方案

这是计算公式性能的直观解决方案 O(N^2)因为它对每次迭代的所有数组求和并且不适用于大型条目。

def solution(A):
    result = []
    for i in xrange(len(A)):
        if sum(A[:i]) == sum(A[i+1:]):
            result.append(i)
    if result == []:
        return -1
    return result

最佳解决方案

这个解决方案是O(N) .谁能解释一下这个解决方案背后的逻辑。

def equi(A):
    result = []
    x=1
    i=1
    r=sum(A)
    for e in A:
        i-=1
        r-=2*e
        if -e==r:
            result.append(-i)
    return result

Answer 1

我相信您发布的解决方案根本不起作用，而且很难理解。所以这是我的看法:

def equi(v):
    left_sum = 0       # sum(v[:p]) at all times.
    right_sum = sum(v) # sum(v[p+1:]) at all times.

    for i in xrange(len(v)):
        right_sum -= v[i]
        if left_sum == right_sum:
            return i   # your p.
        left_sum += v[i]
    return -1 # Because, there may not be an equilibrium index at all.

基本上，无需在循环的每次迭代中重新计算 sum(left side) 和 sum(right side)，您可以通过简单的数学计算得出它们。

状态在某个点，有一个大小为 n 的数组:

pos1 = i
left_sum1 = v[0] + v[1] + ... + v[i-1]
right_sum1 = v[i+1] + v[i+2] + ... + v[n-1]

现在让我们向前一步，看看我们应该有什么:

pos2 = i+1
left_sum2 = v[0] + v[1] + ... + v[i]
right_sum2 = v[i+2] + v[i+2] + ... + v[n-1]

现在，发生了什么变化？

left_sum2 - left_sum1 = v[i]
right_sum2 - right_sum1 = -v[i+1]

这可能会令人困惑，但应该清楚地看到，有一些方法可以通过对先前的值进行加减来获得左侧和右侧的总和。