Given an array of integers arr and an integer k, return the total number of continuous subarrays whose sum equals to k.

__Example 1:__

Input: arr = [1,1,1], k = 2

Output: 2

__Example 2:__

Input: arr = [1,2,3], k = 3

Output: 2

To solve this question click here:(https://leetcode.com/problems/subarray-sum-equals-k/)

So this is a **MEDIUM LEVEL** question. When I read this question then I knew that I have solved similar question in the past but still I couldn't solve this on my own. But after searching for a while I came across 3 approaches.

*Brute Force---------------------------->Optimized
O(n^3)------------O(n^2)---------------O(n)*

**Approach 1:**

So this is really very simple approach, in this we just need to run 3 nested loops and then calculate the sum of each subarray and check it with the target(k).

**JAVA CODE:**

```
public static int subaaray(int arr[],int n,int X)
{
int ans=0;
for(int i=0;i<n;i++)
{
for(int j=i;j<n;j++)
{
int sum=0;
for(int k=i;k<=j;k++)
{
sum+=arr[i];
}
if(sum==X)
ans++;
}
}
return ans;
}
```

**Approach 2:**

In this we just removed the last for loop and calculated the sum inside j loop itself.

**JAVA CODE:**

```
public static int subaaray(int arr[],int n,int X)
{
int ans=0;
for(int i=0;i<n;i++)
{
int sum=0;
for(int j=i;j<n;j++)
{
sum+=arr[i];
if(sum==X)
ans++;
}
}
return ans;
}
```

**Approach 3:(Optimized)**

In this we used HashMap to store the cumulative sum of the array.

*Time Complexity: O(n)*

**JAVA CODE:**

```
public static int subarray(int arr[],int n,int k)
{
HashMap<Integer,Integer> hm=new HashMap<>();
hm.put(0,1); // it is imp to put 0 initially in the hashmap
int ans=0,sum=0;
for(int i=0;i<n;i++)
{
sum+=arr[i];
if(hm.containsKey(sum-k))
ans+=hm.get(sum-k);
hm.put(sum,hm.getOrDefault(sum,0)+1);
}
return ans;
}
```

## Top comments (0)