Count subarrays with sum = k
Hard
Java
Arrays
22 views
Problem Statement
Task: return how many subarrays have sum exactly k (negative numbers allowed). Use prefix sum + hashmap.
Input Format
An integer n (size of array)
Then n integers (array elements, can be negative)
Then an integer k (target sum)
Then n integers (array elements, can be negative)
Then an integer k (target sum)
Output Format
An integer: number of subarrays whose sum is exactly k.
Example
5 1 2 3 -2 5 5
2
Constraints
• n ≥ 1
• Elements can be negative, zero, or positive
• Use prefix sum + HashMap
• Elements can be negative, zero, or positive
• Use prefix sum + HashMap
Concept Explanation
We use prefix sums to track sums up to each index.
If currentPrefixSum - k has appeared before,
then there exists a subarray ending here with sum k.
If currentPrefixSum - k has appeared before,
then there exists a subarray ending here with sum k.
Step-by-Step Explanation
1.Read n, array elements, and k.
2.Create a HashMap to store:
• key → prefix sum
• value → how many times this prefix sum occurred
3.Put (0, 1) in the map (base case).
4.Initialize prefixSum = 0 and count = 0.
5.Loop through the array:
• Add current element to prefixSum.
• Check if (prefixSum - k) exists in the map:
• If yes, add its frequency to count.
• Update map: increase count of prefixSum.
6.After loop ends, print count.
2.Create a HashMap to store:
• key → prefix sum
• value → how many times this prefix sum occurred
3.Put (0, 1) in the map (base case).
4.Initialize prefixSum = 0 and count = 0.
5.Loop through the array:
• Add current element to prefixSum.
• Check if (prefixSum - k) exists in the map:
• If yes, add its frequency to count.
• Update map: increase count of prefixSum.
6.After loop ends, print count.
Concept Explanation
We use prefix sums to track sums up to each index.
If currentPrefixSum - k has appeared before,
then there exists a subarray ending here with sum k.
If currentPrefixSum - k has appeared before,
then there exists a subarray ending here with sum k.
Step-by-Step Explanation
1.Read n, array elements, and k.
2.Create a HashMap to store:
• key → prefix sum
• value → how many times this prefix sum occurred
3.Put (0, 1) in the map (base case).
4.Initialize prefixSum = 0 and count = 0.
5.Loop through the array:
• Add current element to prefixSum.
• Check if (prefixSum - k) exists in the map:
• If yes, add its frequency to count.
• Update map: increase count of prefixSum.
6.After loop ends, print count.
2.Create a HashMap to store:
• key → prefix sum
• value → how many times this prefix sum occurred
3.Put (0, 1) in the map (base case).
4.Initialize prefixSum = 0 and count = 0.
5.Loop through the array:
• Add current element to prefixSum.
• Check if (prefixSum - k) exists in the map:
• If yes, add its frequency to count.
• Update map: increase count of prefixSum.
6.After loop ends, print count.
Input / Output Format
Input Format
An integer n (size of array)
Then n integers (array elements, can be negative)
Then an integer k (target sum)
Then n integers (array elements, can be negative)
Then an integer k (target sum)
Output Format
An integer: number of subarrays whose sum is exactly k.
Constraints
• n ≥ 1
• Elements can be negative, zero, or positive
• Use prefix sum + HashMap
• Elements can be negative, zero, or positive
• Use prefix sum + HashMap
Examples
Input:
5
1 2 3 -2 5
5
Output:
2
Example Solution (Public)
static int countSubarraysSumK(int[] a,int k){java.util.HashMap<Integer,Integer> freq=new java.util.HashMap<>();freq.put(0,1);int pref=0,ans=0;for(int x:a){pref+=x;ans+=freq.getOrDefault(pref-k,0);freq.put(pref,freq.getOrDefault(pref,0)+1);}return ans;}
Official Solution Code
static int countSubarraysSumK(int[] a,int k){java.util.HashMap<Integer,Integer> freq=new java.util.HashMap<>();freq.put(0,1);int pref=0,ans=0;for(int x:a){pref+=x;ans+=freq.getOrDefault(pref-k,0);freq.put(pref,freq.getOrDefault(pref,0)+1);}return ans;}
Please login to submit solutions.