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

Question

问题

给出了一个由N个整数组成的零索引数组A。该数组的平衡索引是任何整数P，使得<代码>0≤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…100000]。

元素范围：[−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

另一种方法如下：

>

sumA, prevSum, n = sum(A), 0, len(A)

接下来让我们考虑每一次迭代会发生什么。我们声明一个变量，例如rem，它是（sumA-prevSum-a[i]）的值。本质上，在每次迭代中，我们都希望从数组的和中删除前一个和（prevSum或leftSum），并删除当前值。

然后我们检查是否rem==preSum。如果这是true，我们返回索引，如果是false，我们重复这个循环，直到数组中的所有元素都被检查到这一点，我们返回一个Falsy值。

这里有相关代码

Answer 2

O（n）解决方案有点太聪明了，有点模糊，但它工作得很好。我已经用有意义的变量名重写了它，并将一些东西移动了一下，以使它的工作原理更加清晰。

def equilibriums(A):               # line 1
    result = []                    # line 2
    difference = sum(A)            # line 3
    
    for p in range(len(A)):        # line 4
        
        difference -= 2*A[p]       # line 5
        
        if difference == -A[p]:    # line 6
            result.append(p)       # line 7
        
    return result                  # line 8

现在解释一下。让

left  = 0,
right = A[0] + A[1] + ... + A[N-2] + A[N-1] = sum(A), and
difference = right - left = sum(A) - 0 = sum(A)    # <-- explains line 3

当将A[0]从right中删除并添加到↓中时，差异将按2*A[0]向下移动。如果将A[1]从right移动到↓，差异将按2*A[1]向下移动。每当元素A[p]被移动时，差异将按2*A[p]向下移动。这解释了第4行和第5行。

现在，在平衡指数P，我们有：

A[0] + A[1] + ... + A[P−1] = A[P+1] + ... + A[N−2] + A[N−1]                # definition
                           = A[P+1] + ... + A[N−2] + A[N−1] + A[P] - A[P]  # add A[P]-A[P]
                           = A[P] + A[P+1] + ... + A[N−2] + A[N−1] - A[P]  # rearrange
\---- but this = left ---/   \--------- and this = right --------/

或者，

left = right - A[P]

和

difference = right - left                 # definition
           = right - (right - A[P])       # substitute
           = A[P]                         # simplify

如果我们将A[P]从right移动到↓，差异将下降2*A[P]，现在

difference = A[P] - 2*A[P] = -A[P]

也就是说，当平衡点从right移动到now时，差异从A[P]移动到-A[P]。因此，如果差异==-A[P]，那么P就是一个均衡索引。这解释了第6行中的测试。

注意，左和右并不是算法真正需要的。它们只是用来解释的。

equilibriums([1,2,3,0,1,0,0,0,0,1,6])  ==> returns [5, 6, 7, 8]

Answer 3

我相信你发布的解决方案根本不起作用，而且很难理解。以下是我的看法：

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（左边）和sum（右边），你可以用简单的数学计算出来。

用大小为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]

这可能会让人困惑，但应该清楚地看到，通过对之前的值进行加减，可以得到任意点的左右两边之和。