DEV Community

Tisha Agarwal
Tisha Agarwal

Posted on

3 1

Subarray Sum Equals K

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;
    }
Enter fullscreen mode Exit fullscreen mode

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;
    }
Enter fullscreen mode Exit fullscreen mode

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;

    }
Enter fullscreen mode Exit fullscreen mode

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

Top comments (0)