Znajdź numer ciągłej podtablicy o sumie zerowej

Question

Podałeś tablicę i musisz podać liczbę ciągłych podbarw, których suma wynosi zero.

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. 

Z O (n^2) można to zrobić. Próbuję znaleźć rozwiązanie poniżej tej złożoności.

Answer 1

nie wiem co złożoność moją sugestią byłoby ale mam pomysł :)
Co można zrobić, to spróbować zmniejszyć element z głównej tablicy, które nie są w stanie przyczynić się dla Ciebie rozwiązanie Załóżmy elementów są -10, 5, 2, -2, 5,7 ,-5, 9,11,19
więc widać, że -10,9,11 and 19 są elementem
że nigdy nie odeszły być przydatna do sum 0 w przypadku
więc spróbuj usunąć -10,9,11, and 19 z głównej tablicy do tego, co można zrobić zrobić to

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 

więc w końcu masz tablicę, która zawiera -2, -5,5,5,17 utwórz wszystkie możliwe podrzędne jej formy i sprawdź sumę = 0
(Uwaga: jeśli twoja wejściowa tablica zawiera 0, dodaj wszystkie 0 w ostateczna array)

Answer 2

czuję to może być rozwiązany za pomocą DP: Niech państwo być: DP [i] [j] oznacza liczbę sposobów j można wytwarzać stosując wszystkie subarrays kończąc na I!

przejść:

dla każdego elementu w początkowym etapie,

zwiększenia liczby sposobów tworząc Element[i] użyciem i elementy od 1, tj pomocą subarray długości 1 wychodząc z I i kończąc I tj

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

to dla każdej j w zakresie [-mod (najwyższy wielkość każdego elementu) mod (najwyższy wielkość każdego elementu)]

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

Wtedy odpowiedź będzie sumą wszystkich DP [i] [0] (wiele sposobów, tworząc 0 użyciem subarrays kończąc na I), gdzie i zmienia się od 1 do liczby elementów

Złożoność jest O (maksymalna wielkość MOD dowolnego elementu * liczba elementów)

Answer 3

Weź pod uwagę S [0..N] - prefix sums swojej tablicy, tj. S [k] = A [0] + A [1] + ... + A [k-1] dla k od 0 do N.

Teraz suma elementów od L do R-1 wynosi zero i f i tylko jeśli S [R] = S [L]. Oznacza to, że musisz znaleźć liczbę indeksów 0 < = L < R < = N takich, że S [L] = S [R].

Ten problem można rozwiązać za pomocą tabeli skrótów. Iteruj po elementach S [] zachowując dla każdej wartości X liczbę razy, gdy zostało spełnione w już przetworzonej części S []. Liczby te powinny być przechowywane w mapie mieszania, gdzie liczba X jest kluczem, a liczba H [X] jest wartością. Kiedy poznasz nowe elementy S [i], dodaj H [S [i]] do swojej odpowiedzi (te konta zawierają ciągi kończące się elementem (i-1) -st), a następnie zwiększ H [S [i]] o jeden .

Należy zauważyć, że jeśli suma wartości bezwzględnych elementów tablicy jest mała, można użyć prostej tablicy zamiast tabeli mieszania. Złożoność jest średnio liniowa.

tutaj kod:

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

ten może być rozwiązany w czasie liniowej utrzymując tabeli mieszania sum osiągane podczas przechodzenia tablicy. Liczba podzbiorów może być następnie obliczana bezpośrednio na podstawie zrewidowanych sum. Wersja

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)]) 

wyjściowa:

*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