Combining Techniques

You learned prefix sums for range queries. You learned hash maps for fast lookup. What happens when you combine them? Problem: count subarrays with sum equal to $k$.

Brute force: check all $O(n^2)$ subarrays. With prefix sums, each check is $O(1)$, but still $O(n^2)$ total. With hash maps, you can do this in $O(n)$.

The trick: for each prefix sum, count how many previous prefix sums would give a valid subarray. Time: $O(n)$. Space: $O(n)$.