*Given an array a[] = {1, 1 ,1 , -1} . you have to find all the subarrays of the given array whose sum is exactly =* k.

example : a[] = { 1 , 1 , 1 , -1 } and k = 1

Ans = 4 all 3 one's + range from [2,4]

There is an geeks_article for it but the explanation is not good and clear and also without proof .

Can anyone explain me how to solve this problem with some explanation !

Thanks !

Use prefix sums. Let , then the sum of a subarray in [

l,r] is equal tosum[r] -sum[l- 1].If we iterate over all possible pairs (

l,r), we get a complexity ofO(n^{2}).Fix the right boundary, if we maintain the prefix sum of the left boundary in a set, the time complexity is . Note that the possible left boundary is nondecreasing as the right boundary increases, we can handle this with two-pointers technique and thus have a complexity of

O(n).wait...the elements may be negative.

OK, my bad. So ignore the nondecreasing thing.

We can still get $$$O(n)$$$ if we assume hash tables work in $$$O(1)$$$

In this case,

a_{i}isn't necessarily non-negative, so the two-pointer solution doesn't work. You could use a hash table instead of a set to achieve expectedO(n) time.yes , the elements may be negative , 0 or postitive and we have to device a linear complexity.

how to do so ?

Fix the right bound and store the first

rprefixes into a bucket.Then ans should be increased bybucket[k-sum[r]].If we use`map`

the complexity will be .If we use`unordered_map`

(only allowed in C++11 or higher versions) it will beO(n).If we use a hash table then it will be expectedO(n).(Sometimes it may be even slower than !)ok . done. thanks

A simple solution is to traverse all the subarrays and calculate their sum. If sum is equal to the required sum then increment the count of subarrays. Print final count of subarrays.