Subarray Sum with HashMap
The subarray sum equals K problem asks: find number of contiguous subarrays whose sum equals a given target K. This can be solved efficiently using prefix sums and a HashMap in O(n) time.
Concept:
Let prefix sum up to index i be sum[i] = arr[0] + ... + arr[i]. The sum of subarray from index j+1 to i is sum[i] - sum[j]. We want sum[i] - sum[j] = K → sum[j] = sum[i] - K. So for each i, we count how many previous prefix sums equal sum[i] - K.
Java implementation:
public static int subarraySum(int[] nums, int k) {
Map map = new HashMap<>();
map.put(0, 1); // base case: sum 0 appears once
int count = 0, sum = 0;
for (int num : nums) {
sum += num;
int target = sum - k;
count += map.getOrDefault(target, 0);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}
Variants:
- Longest subarray with sum K: store first occurrence of each prefix sum.
- Zero sum subarray: check if any prefix sum repeats or becomes zero.
- Subarray sum divisible by K: use modulo and count frequencies.
Two Minute Drill
- Subarray sum equals K uses prefix sum + HashMap.
- For each prefix sum, count previous prefix sums equal to current sum - K.
- Initialize map with (0,1) to handle subarrays starting at index 0.
- Time O(n), space O(n).
- Critical technique for many subarray problems.
Need more clarification?
Drop us an email at career@quipoinfotech.com