Subarray Sum - Algorithm

Maintain a running prefix sum and a hash map of prefix sum frequencies:

$1.$ Initialize: $prefixSum = 0$, $count = 0$, hash map with $\{0: 1\}$ (empty prefix).

$2.$ For each element, add it to $prefixSum$.

$3.$ Add $freq[prefixSum - k]$ to $count$ (number of valid subarrays ending here).

$4.$ Increment $freq[prefixSum]$ by $1$.

$5.$ Return $count$. The hash map tracks "how many times has each prefix sum occurred?" Time: $O(n)$. Space: $O(n)$.