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)