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 .
Brute force: check all subarrays. With prefix sums, each check is , but still total. With hash maps, you can do this in .
The trick: for each prefix sum, count how many previous prefix sums would give a valid subarray. Time: . Space: .