Given a list of number we want to find Count of Sub Array with Target Sum K.
Example:
A = [1,2,1,4,1,3,7,1,6] K= 7
Answer = 3
Since we can find 3 sub arrays [2,1,4] , [7] , [1,6] whose sum of these sub arrays are equal to the given target sum, 7.
Example:
A = [5,6,4,2,1,9]
K = 10
Ans: 2 since we can find two sub array [6,4] and [1,9] that can add up to 10
Solution:
The key to solving this problem lies in a very important mathematical understanding of what it means the sum of sub array. Mind you the sub array we need to find has to be next to each other elements of the array.
When we closely examine the above diagram, we will soon understand that
Sum(i)-k == Sum(j) if a(j+1) + a(J+2) + a(j+3) … a(i) == k
If we can visualize this then the rest is a simple mater left for dictionaries.
Basically what we need to do after here is we run through a for loop for each item in the given array and we we calculate a running total at each index and we throw them in a dictionary.
We also check if our dictionary contains sum(i) - k and if it does that means we found our first consecutive sum equals to target sum and we keep going until we find all sub array with given sum.
if (nums == null || nums.Length == 0) return 0;
int sum = 0;
int count = 0;
Dictionary<int, int> map = new Dictionary<int, int>();
map.Add(0, 1);
for (int i = 0; i < nums.Length; i++) {
sum += nums[i];
if (map.ContainsKey(sum - k)) {
count += map[sum - k];
}
int val = (map.ContainsKey(sum) ? map[sum] : 0) + 1;
map[sum] = val;
}
return count;