Subarray Sum Problems
Problems involving subarray sums are common in interviews. They test your ability to apply prefix sums, hashing, and two-pointer techniques.
1. Subarray Sum Equals K
Find number of subarrays whose sum equals a given value k.
public static int subarraySum(int[] nums, int k) {
Map map = new HashMap<>();
map.put(0, 1);
int sum = 0, count = 0;
for (int num : nums) {
sum += num;
int diff = sum - k;
count += map.getOrDefault(diff, 0);
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}
2. Subarray Sum with Zero
Check if any subarray has sum zero. Use a hash set to store running sums; if we see a sum again, there's a zero-sum subarray.
public static boolean hasZeroSumSubarray(int[] nums) {
Set set = new HashSet<>();
int sum = 0;
for (int num : nums) {
sum += num;
if (sum == 0 || set.contains(sum)) return true;
set.add(sum);
}
return false;
}
3. Longest Subarray with Sum K
Similar to counting, but store first occurrence of each prefix sum.
Two Minute Drill
- Subarray sum problems are solved with prefix sums + hash maps.
- For sum equals k, store frequency of prefix sums; count += freq[sum - k].
- For zero-sum subarray, check if prefix sum repeats or becomes zero.
- Time O(n), space O(n).
Need more clarification?
Drop us an email at career@quipoinfotech.com