Найти в массиве все числа, сумма которых равна нулю

Вот решение на Python, работающее за O(n³):

def conSumZero(input):
    take = [False] * len(input)

    for i in range(len(input)):
        for j in range(i+1, len(input)):
            if sum(input[i:j]) == 0:
                for k in range(i, j):
                    take[k] = True;

    return numpy.where(take, input)

РЕДАКТИРОВАТЬ: теперь более эффективно! (Не уверен, что это вполне O (n²); обновлю, как только закончу вычислять сложность.)

def conSumZero(input):
    take = [False] * len(input)
    cs = numpy.cumsum(input)
    cs.insert(0,0)

    for i in range(len(input)):
        for j in range(i+1, len(input)):
            if cs[j] - cs[i] == 0:
                for k in range(i, j):
                    take[k] = True;

    return numpy.where(take, input)

Разница здесь в том, что я предварительно вычисляю частичные суммы последовательности и использую их для вычисления сумм подпоследовательностей - начиная с sum(a[i:j]) = sum(a[0:j]) - sum(a[0:i]) - вместо того, чтобы повторять каждый раз.

Почему бы просто не хешировать инкрементные итоговые суммы и не обновлять их индексы по мере прохождения массива, причем победителем становится тот, у кого самый большой диапазон индексов. O(n) временная сложность (при средней сложности хеш-таблицы).

       [2, 3, -3, 4, -4, 5, 6, -6, -5, 10]
sum  0  2  5   2  6   2  7  13  7   2  12

The winner is 2, indexed 1 to 8!

Чтобы также гарантировать точный аналог непрерывного подмассива для каждого числа в выходном массиве, я пока не вижу способа проверить/хэшировать все подпоследовательности сумм в подмассивах-кандидатах, что увеличило бы временную сложность до O(n^2).

Основываясь на примере, я предположил, что вы хотите найти только те, где 2 значения вместе составляют 0, если вы хотите включить те, которые в сумме дают 0, если вы сложите больше из них вместе (например, 5 + -2 + - 3), то вам нужно будет уточнить ваши параметры немного больше.

Реализация зависит от языка, но вот пример javascript, показывающий алгоритм, который вы можете реализовать на любом языке:

var inputArray = [2, 3, -3, 4, -4, 5, 6, -6, -5, 10];
var ouputArray = [];

for (var i=0;i<inputArray.length;i++){
    var num1 = inputArray[i];

    for (var x=0;x<inputArray.length;x++){
        var num2 = inputArray[x];
        var sumVal = num1+num2;
        if (sumVal == 0){
            outputArray.push(num1);
            outputArray.push(num2);

        }

    }
}

Это проблема, которую вы пытаетесь решить?

Учитывая последовательность , найдите максимизация такой, что

Если да, то вот алгоритм ее решения:

let $U$ be a set of contiguous integers
for each contiguous $S\in\Bbb Z^+_{\le n}$
    for each $\T in \wp\left([i,j)\right)$
      if $\sum_{n\in T}a_n = 0$
        if $\left|S\right| < \left|U\left$
          $S \to u$

вернуть $U$

(Будет обновлен с полным латексом, как только у меня будет такая возможность.)