Count subarrays with sum = k
Java
Hard
5 views
Problem Description
Task: return how many subarrays have sum exactly k (negative numbers allowed). Use prefix sum + hashmap.
Output Format
Return value
Constraints
O(n) time expected.
Official Solution
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;}
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!