# Count Subarray with Sum Equal to K using Map in C++

This article will see how we can count the total number of subarray with a sum equal to K in linear time complexity using a hash table.

In this problem, we are given an array of size n  and an integer k. And we have to find the number of subarray with a sum equal to k.

A Subarray is a part or section of an array. It is composed of contiguous blocks of indices of the original array. In simple terms, we can say subarray is a part of a given array.

Example:

`for an array=[10, 20, 30, 40] the subarrays are , , , , [10, 20], [10, 20, 30], [30, 40], [20, 30], `

`[20, 30, 40] and [10, 20, 30, 40].`

So, for an array of size n, we can have a total of n*(n+1)/2 subarrays.

Now, for this problem, we are given an array of integers of size n and an integer k. We have to find the total number of subarrays whose sum is equal to k.

Example:

```Example 1:INPUT: array=[1,2,3] k=3OUTPUT: 2Example 2:INPUT: array=[3,4,7,2,-3,1,4,2] k=4
OUTPUT: 4```

## Brute Force Algorithm

The brute force or simple approach to solving the problem is to check the sum of all the subarray in the array. And while counting the sum of all arrays we can keep a counter to count the number of subarray with a sum equal to k. This approach will make use of nested loops.

The Time complexity of this algorithm in the worst case will be O(n2).

Now to find the sum of all n*(n-1)/2 subarrays for a greater value of n the algorithm will take more time.

## Efficient Algorithm

This problem can be solved in linear time complexity. The idea is to make use of extra space and reduce the time complexity.

- Use a unordered_map to keep the frequency of subarray sums we encounter during traversing the array.

- And while traversing the array check if the (sum-k) value is present in the map or not.

- If the value is present, then we have a subarray with a sum equal to k.

- add the frequency count of the value found to our result variable.

|<-------------------sum = K --------------->|

 Array 3 4 7 2 -3 1 4 2 Sum 0 3 7 14 16 13 14 18 20

|<-----------------------------  sum = (Y- k) -------------------------------->|

|<----------------------------------------------------------- Sum = Y ---------------------------------------------------------->|

From the above diagram, if sum (y-k) is present in the map then we definitely have a subarray with a sum equal to k.

## Program

```#include
#include
#include
using namespace std;

int subarraySum(vector &array, int k)
{
unordered_map<int, int> m; //assign map m
m.insert({0, 1});          // insert initial sum 0 in map

int sum = 0, result = 0;

for (int i = 0; i < array.size(); i++)
{
sum += array[i]; //sum of array elements

if (m[sum - k]) //check if (sum - k) in map
result += m[sum - k];

m[sum]++;
}
return result;
}

int main()
{
vector array{3, 4, 7, 2, -3, 1, 4, 2}; //assign array
int k = 7;                                  //sum value equal to k
int result = subarraySum(array, k);
cout << "Count of Subarray with sum k : "result << endl;
return 0;
}```

### OUTPUT:

`Count of Subarray with sum k : 4`

Submitted by Ashutosh Sunil Rane (AshuRane09)