Найти номер непрерывного подмассива, имеющего нулевую сумму

Question

Вы дали массив, и вы должны указать количество непрерывных субарарей, сумма которых равна нулю.

example: 
1) 0 ,1,-1,0 => 6 {{0},{1,-1},{0,1,-1},{1,-1,0},{0}}; 
2) 5, 2, -2, 5 ,-5, 9 => 3. 

С O (n^2) это можно сделать. Я пытаюсь найти решение ниже этой сложности.

Answer 1

Я не знаю, что сложность мое предложение было бы, но у меня есть идея :)
Что вы можете сделать, это попытаться уменьшить элемент из основного массива, которые не способны внести свой вклад в вам решение Предположим элементов являются -10, 5, 2, -2, 5,7 ,-5, 9,11,19
, так что вы можете увидеть, что -10,9,11 and 19 являются элементом
, которые никогда не пошли бы полезно сделать sum 0 в вашем случае
так попытайтесь удалить -10,9,11, and 19 из основного массива сделать это то, что вы можете сделать, это

1) create two sub array from your main array 
`positive {5,7,2,9,11,19}` and `negative {-10,-2,-5}` 
2) remove element from positive array which does not satisfy condition 
    condition -> value should be construct from negative arrays element 
    or sum of its elements 
    ie. 
     5 = -5 //so keep it //don't consider the sign 
     7 = (-5 + -2) // keep 
     2 = -2 // keep 
     9 // cannot be construct using -10,-2,-5 
     same for all 11 and 19 
3) remove element form negative array which does not satisfy condition 
     condition -> value should be construct from positive arrays element 
     or sum of its elements 
    i.e. -10 // cannot be construct so discard 
     -2 = 2 // keep 
     -5 = 5 // keep 

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

Answer 2

Я чувствую, что это можно решить с помощью DP: Пусть состояние будет: DP [i] [j] представляет количество путей j, которые могут быть сформированы с использованием всех подмассивов, заканчивающихся на i!

Переходов:

для каждого элемента в начальной стадии,

увеличить число способов формирования Element[i] с помощью I Элементов на 1 т с использованием подмассива длиной 1, начиная с I и заканчивая я т.е.

DP[i][Element[i]]++; 

то для каждого J в диапазоне [-Mod (наивысшая величина любого элемента), Mod (наивысшая величина любого элемента)]

DP[i][j]+=DP[i-1][j-Element[i]]; 

Тогда ваш ответ будет сумма всех DP [я] [0] (Количество способов формирования 0, используя подмассива оканчивающиеся на I), где я колеблется от 1 до Количество элементов

Сложность - O (MOD наивысшая величина любого элемента * Количество элементов)

Answer 3

Рассмотрим S [0..N] - prefix sums вашего массива, то есть S [k] = A [0] + A [1] + ... + A [k-1] для k от 0 до N.

Теперь сумма элементов из L в R-1 равна нулю i f и только если S [R] = S [L]. Это означает, что вам нужно найти число индексов 0 < = L < R < = N такое, что S [L] = S [R].

Эта проблема может быть решена с помощью хеш-таблицы. Итерации по элементам S [], сохраняя при каждом значении X количество раз, которое оно выполнялось в уже обработанной части S []. Эти подсчеты должны храниться в хэш-карте, где число X является ключом, а значение H [X] является значением. Когда вы встретите новые элементы S [i], добавьте H [S [i]] к вашему ответу (эта учетная запись для подстрок, заканчивающихся на элемент (i-1) -st), затем увеличивайте H [S [i]] на один ,

Обратите внимание, что если сумма абсолютных значений элементов массива мала, вы можете использовать простой массив вместо хеш-таблицы. Сложность в среднем является линейной.

Вот код:

long long CountZeroSubstrings(vector<int> A) { 
    int n = A.size(); 

    vector<long long> S(n+1, 0); 
    for (int i = 0; i < n; i++) 
     S[i+1] = S[i] + A[i]; 

    long long answer = 0; 
    unordered_map<long long, int> H; 
    for (int i = 0; i <= n; i++) { 
     if (H.count(S[i])) 
      answer += H[S[i]]; 
     H[S[i]]++;  
    } 

    return answer; 
} 

Answer 4

Это может быть решена за линейное время, сохраняя хэш-таблицу сумм, достигнутых во время обхода массива. Затем количество подмножеств может быть непосредственно вычислено из подсчета повторных сумм. версия

Haskell:

import qualified Data.Map as M 
import Data.List (foldl') 

f = foldl' (\b a -> b + div (a * (a + 1)) 2) 0 . M.elems . snd 
    . foldl' (\(s,m) x -> let s' = s + x in case M.lookup s' m of 
          Nothing -> (s',M.insert s' 0 m) 
          otherwise -> (s',M.adjust (+1) s' m)) (0,M.fromList[(0,0)]) 

Выход:

*Main> f [0,1,-1,0] 
6 

*Main> f [5,2,-2,5,-5,9] 
3 

*Main> f [0,0,0,0] 
10 

*Main> f [0,1,0,0] 
4 

*Main> f [0,1,0,0,2,3,-3] 
5 

*Main> f [0,1,-1,0,0,2,3,-3] 
11