Prefix Sum + HashMap
Count matching past prefix sums to find how many subarrays hit the target.
0 of 3 problems solved
Prefix Sum + HashMap
Count matching past prefix sums to find how many subarrays hit the target.
- •Is this about exact subarray sums rather than a valid window?
- •Can prefix sums convert the problem into past-total lookups?
- •Did I seed the map with prefix sum 0?
Subarray Sum Equals K looks like a window problem, but it is not safe to use sliding window when negative numbers might appear. The better idea is prefix sum plus HashMap. As you walk through the array, keep a running total. If the current prefix sum is current, then any earlier prefix sum equal to current minus k creates a subarray summing to k. So the HashMap is really counting how many useful past totals are waiting for you.
You are not searching for subarrays directly. You are counting matching prefix sums.
- 1Keep a running prefix sum while scanning the array.
- 2Use a HashMap to count how many times each prefix sum has appeared.
- 3At each step, look for prefixSum - k in the map.
- 4Add that count to your answer, then record the current prefix sum in the map.
Forgetting to seed the map with prefix sum 0 means you miss subarrays that start at index 0.
Range Sum Query - Immutable
Build prefix[i+1] = prefix[i] + nums[i] once in the constructor. Any range sum [l, r] is then prefix[r+1] - prefix[l] in O(1).
Count of Range Sum
Compute prefix sums, then use divide-and-conquer merge sort. During the merge step, count pairs whose prefix sum difference falls inside [lower, upper].