Какой алгоритм лучше использовать для этой проблемы?

Question

Равновесный индекс последовательности - это такой индекс, что сумма элементов при более низких индексах равна сумме элементов при более высоких индексах. Например, в последовательности A:

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

3 является индексом равновесия, потому что:

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

6 также является индексом равновесия, потому что:

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

(сумма нулевых элементов равна нулю) 7 не является индексом равновесия, поскольку он не является допустимым индексом последовательности А. Если у вас все еще есть сомнения, это точное определение: целое число k является индексом равновесия последовательности, если и только если и.

Предположим, что сумма нулевых элементов равна нулю. Написать функцию

int equi(int[] A);

что для данной последовательности возвращает ее индекс равновесия (любой) или -1, если индексов равновесия не существует. Предположим, что последовательность может быть очень длинной.

Answer 1

1. Рассчитать общую сумму всех элементов в A
2. Для каждого индекса i, вычислить сумму элементов от A[0] до A[i - 1] до суммыравно (totalSum - A[i]) / 2.

Обратите внимание, что сумма элементов от A[0] до A[i - 1] может отслеживаться как текущая сумма, что означает, что сложность всего алгоритма равна O (п).Реализация в виде кода оставлена ​​читателю в качестве упражнения.

Answer 2

Псевдокод - наихудший случай - 2 прохода через 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

Answer 3

Вот решение, которое использует O(n) память.Вычислить S[i] = A[0] + A[1] + ... + A[i].Тогда сумма подпоследовательности [i, j] равна Sum(i, j) = S[j] - S[i - 1] (S[x < 0] = 0).

Так что для каждого i от 0 до A.Length - 1 проверьте, если Sum(0, i - 1) = Sum(i + 1, A.Length - 1).

На самом деле, если вам разрешено уничтожить данный массив, вам даже не нужно S, вы можете сделать все это за A.

Answer 4

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

sumleft = 0

sumright = 0

дляЯ в диапазоне (len (a)):

for j in range(i+1,len(a)):

    sumright += a[j]

if sumright == sumleft:

    print i

sumleft += a[i]

sumright = 0