Problem Statement
Explain how to count sub-arrays whose sum equals K in an integer array (with positive and negative values).
Explanation
Use prefix‐sum and hash map: as you iterate, maintain sum so far. For each index j, you want i where prefixSum[j]−prefixSum[i] = K ⇒ prefixSum[i] = prefixSum[j]−K. So check map for prefixSum[j]−K and increment count by value. Store/update current prefixSum in map. Time O(n), space O(n). Handles negatives and positives.
Code Solution
SolutionRead Only
Map<Integer,Integer> map=new HashMap<>(); map.put(0,1); int sum=0,count=0; for(int x:arr){ sum+=x; if(map.containsKey(sum-K)) count += map.get(sum-K); map.put(sum, map.getOrDefault(sum,0)+1); } return count;