Prefix Sum + Hash Map: The O(n) Superpower

Concepts: pyPrefixHashMap, pySubarrayCount, pyComplementLookup

This is the combination that shows up in more mid-to-senior level interviews than almost any other pattern. The setup is always the same: you need to count (or find) subarrays satisfying some sum condition. Brute force checks every pair (i, j): O(n^2). The insight is that any subarray sum condition can be restated as a relationship between two prefix sum values. Once you have that relationship, you use a hash map to look up the complement in O(1). Total: O(n) time, O(n) space. The General Framework The reason this works in one pass, left to right, is that when you process element at index j (making prefix = prefix[j+1] in the 1-indexed sense), all the previous prefix sums (for indices i = 0 through j) are already recorded in freq. So freq[prefix - target] gives you the count of valid left