问题描述:

Equilibrium index of a sequence is an index such that the sum of elements at lower indexes is equal to the sum of elements at higher indexes. For example, in a sequence A:

`A[0]=-7 A[1]=1 A[2]=5 A[3]=2 A[4]=-4 A[5]=3 A[6]=0`

3 is an equilibrium index, because:

`A[0]+A[1]+A[2]=A[4]+A[5]+A[6]`

6 is also an equilibrium index, because:

`A[0]+A[1]+A[2]+A[3]+A[4]+A[5]=0`

(sum of zero elements is zero) 7 is not an equilibrium index, because it is not a valid index of sequence A.

If you still have doubts, this is a precise definition: the integer k is an equilibrium index of a sequence if and only if and .

Assume the sum of zero elements is equal zero. Write a function

`int equi(int[] A);`

that given a sequence, returns its equilibrium index (any) or -1 if no equilibrium indexes exist. Assume that the sequence may be very long.

- Calculate the total sum of all of the elements in
`A`

- For every index
`i`

, calculate the sum of the elements from`A[0]`

to`A[i - 1]`

, until the sum is equal to`(totalSum - A[i]) / 2`

.

Note that the sum of elements from `A[0]`

to `A[i - 1]`

can be tracked as a running total, which means that the complexity of the whole algorithm is O(n). Implementing as code is left as an exercise for the reader.

Here's a solution that uses `O(n)`

memory. Compute `S[i] = A[0] + A[1] + ... + A[i]`

. Then the sum of a subsequence `[i, j]`

is `Sum(i, j) = S[j] - S[i - 1]`

(`S[x < 0] = 0`

).

So for each `i`

from `0`

to `A.Length - 1`

check if `Sum(0, i - 1) = Sum(i + 1, A.Length - 1)`

.

In fact, if you're allowed to destroy the given array, you don't even need `S`

, you can do it all in `A`

.

Pseudocode - worst case is 2 passes through A.

```
R = sum(A)
L = e = 0
for i = 0 .. A.size
L+=e
R-=(e=A[i])
return i if L==R
end
return NULL
```

a = (-7, 1, 5, 2, -4, 3, 0)

sumleft = 0

sumright = 0

for i in range(len(a)):

`for j in range(i+1,len(a)): sumright += a[j] if sumright == sumleft: print i sumleft += a[i] sumright = 0`

您可能感兴趣的文章：

- c++ - access to sms inbox
- flash - AS3 - Repeating a MovieClip quickly before it has finished
- ruby on rails - RoR custom routing/Method/View problem all methods come back as undefined
- Where does stack for each program begin in memory?
- Zend Framework routes.ini with multiple routes but the same module/controller/action destination?
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?

随机阅读：

**推荐内容**-

**热点内容**