Find the number of continuous subarrays having zero sum

Question

You specified an array, and you need to specify the number of continuous subaras, the sum of which is 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. 

With O (n ^ 2) this can be done. I am trying to find a solution below this complexity.

Answer 1

I don’t know how difficult my proposal will be, but I have an idea :)
What you can do is try to reduce the element from the main array, which is not able to contribute to the solution of the problem, suppose that the elements are -10, 5, 2, -2, 5,7 ,-5, 9,11,19
so you can see that -10,9,11 and 19 are elements that are never useful to make sum 0 in your case
so try removing -10,9,11, and 19 from the main array for this you can do

 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 ie -10 // cannot be construct so discard -2 = 2 // keep -5 = 5 // keep 

so finally you got an array that contains -2, -5,5,7,2, create all possible auxiliary arrays and check for sum = 0
(Note if your input array contains 0, add all 0 to the final array)

Answer 2

Consider S [0..N] - the prefix sums of your array, that is, S [k] = A [0] + A [1] + ... + A [k-1] for k from 0 to N.

Now the sum of elements from L to R-1 is equal to zero if and only if S [R] = S [L]. This means that you need to find the number of indices 0 <= L <R <= N, such that S [L] = S [R].

This problem can be solved with a hash table. Iterate over the elements of S [], saving for each value of X the number of times that it was performed in the already processed part of S []. These calculations should be stored in a hash map where the number X is the key and the value H [X] is the value. When you meet new S [i] elements, add H [S [i]] to your answer (this account is for substrings ending in (i-1) -st), then increase H [S [i]] by one.

Note that if the sum of the absolute values ​​of the elements of the array is small, you can use a simple array instead of a hash table. Complexity is linear on average.

Here is the code:

 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 3

This can be solved in linear time by maintaining a hash table of the amounts reached during the array traversal. Then, the number of subsets can be directly calculated from repeated sums.

Haskell Version:

 import qualified Data.Map as M import Data.List (foldl') f = foldl' (\ba -> 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)]) 

Output:

 *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 

Answer 4

I feel that this can be solved with DP: Let the state be: DP [i] [j] represents the number of paths j that can be formed using all subarrays ending in i!

Transitions:

for each element of the initial step,

Increase the number of ways of forming Element[i] using elements i by 1, that is, using a subarray of length 1, starting with i and ending with i ie

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

then for each j in Range [-Mod (the largest value of any element), Mod (the largest value of any element)]

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

Then your answer will be the sum of all DP [i] [0] (the number of ways to form 0 using subarrays ending in i), where I change from 1 to the number of elements

Difficulty - O (maximum MOD value of any element * Number of elements)

Answer 5

C # version of @ stgatilov's answer fooobar.com/questions/1226582 / ... with readable variables:

  int[] sums = new int[arr.Count() + 1]; for (int i = 0; i < arr.Count(); i++) sums[i + 1] = sums[i] + arr[i]; int numberOfFragments = 0; Dictionary<int, int> sumToNumberOfRepetitions = new Dictionary<int, int>(); foreach (int item in sums) { if (sumToNumberOfRepetitions.ContainsKey(item)) numberOfFragments += sumToNumberOfRepetitions[item]; else sumToNumberOfRepetitions.Add(item, 0); sumToNumberOfRepetitions[item]++; } return numberOfFragments; 

If you want to have the sum not only zero, but also any number k, here is a hint:

  int numToFind = currentSum - k; if (sumToNumberOfRepetitions.ContainsKey(numToFind)) numberOfFragments += sumToNumberOfRepetitions[numToFind];