数组中的索引，使其前缀总和等于其后缀总和-最佳解决方案 [英] Index in an array such that its prefix sum equals its suffix sum - best solution

问题描述

问题

给出了一个由N个整数组成的零索引数组A。该阵列的平衡指数是任何整数P，使得 0≤P < N 和较低索引元素的总和等于较高索引元素的总和。

A zero-indexed array A consisting of N integers is given. An equilibrium index of this array is any integer P such that 0 ≤ P < Nand the sum of elements of lower indices is equal to the sum of elements of higher indices.

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

假定零元素之和等于0。如果 P = 0 或如果 P = N-1 。

Sum of zero elements is assumed to be equal to 0. This can happen if P = 0 or if P = N−1.

N的范围： [0 ... 100,000] 。

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

复杂度：最坏情况下的时间 O（N）

Complexity: worst-case time O(N)

我的5分钟解决方案

这是通过计算公式的性能为 O（N ^ 2），因为它会将每次迭代的所有数组求和，并且不适用于大条目。

This is the intuitive solution by computing the formula performance is O(N^2) as it sums the all array for each iteration and it doesnt work for large entries.

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）。有人可以解释此解决方案背后的逻辑。

This solution is O(N). Can someone explain the logic behind this solution.

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

推荐答案

我认为您发布的解决方案根本不起作用，无论如何也很难理解。
所以这是我的看法：

I believe the solution you posted does not work at all, and it's very difficult to understand anyways. So here's my take on it:

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（右侧）循环，您可以用简单的数学方法弄清楚它们。

Basically, instead of recalculating sum(left side) and sum(right side) on every iteration of your loop, you can figure them out with simple math.

在某个点上的状态，大小为n：

State at some point, with an array of size n:

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

现在，我们向前迈一步，检查一下我们应该拥有什么：

Now let's go forward one step and check what we should have:

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

现在，发生了什么变化？

Now, what did change?

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

这可能会令人困惑，但是应该很清楚地看到，有某种方法可以通过在任意点上加上和减去以前的值来获取左侧和右侧的总和。

It may be confusing, but it should be plain to see that there is some way to get the sums of the left and right side at any point by adding and substracting to your previous values.

这篇关于数组中的索引，使其前缀总和等于其后缀总和-最佳解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！