## What is it? Find the total number of contiguous subarrays whose elements sum to exactly `k`. Uses a prefix sum combined with a HashMap for an O(n) solution. ## How it works - Maintain a running `prefixSum = 0` and a HashMap `count` initialized with `{0: 1}` - For each element: - `prefixSum += arr[i]` - If `prefixSum - k` is in the map → add its count to the result (a subarray ending here sums to k) - Increment `count[prefixSum]` in the map - Return result **Why:** `sum(l, r) = k` iff `prefix[r+1] - prefix[l] = k` iff `prefix[l] = prefix[r+1] - k` ## When to use - Count subarrays with a target sum (LeetCode 560) - Count subarrays with at most k distinct elements - Any "count subarrays with sum constraint" problem ## Key Points - O(n) time and space - The `{0: 1}` initialization handles subarrays starting from index 0 - Works for negative numbers (unlike sliding window which requires non-negative values)