This content originally appeared on DEV Community and was authored by Tisha Agarwal
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;
}
This content originally appeared on DEV Community and was authored by Tisha Agarwal
Tisha Agarwal | Sciencx (2022-02-10T13:51:57+00:00) Subarray Sum Equals K. Retrieved from https://www.scien.cx/2022/02/10/subarray-sum-equals-k/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.