Find number of continuous subarray having sum zero

Question

You have given a array and You have to give number of continuous subarray which the sum 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) it can be done.I am trying to find the solution below this complexity.

Answer 1

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

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

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

Note that if sum of absolute values of array elements is small, you can use a simple array instead of hash table. The 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 2

This can be solved in linear time by keeping a hash table of sums reached during the array traversal. The number of subsets can then be directly calculated from the counts of revisited sums.

Haskell version:

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

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 3

C# version of @stgatilov answer https://stackoverflow.com/a/31489960/3087417 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 sum not only zero but any number k, here is the hint:

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