Prefix sums turn a question about subarrays into a question about pairs of positions: the sum of nums[i..j] is prefix[j+1] - prefix[i]. Combine that with a hash map of prefix sums seen so far, and you can count matching pairs in one pass.
Given a list of integers nums and an integer k, return the number of contiguous, non-empty subarrays whose elements sum to k.
Examples
Input: nums = [1, 1, 1], k = 2
Output: 2
Explanation: [1, 1] starting at index 0 and [1, 1] starting at index 1.
Input: nums = [1, -1, 0], k = 0
Output: 3
Explanation: [1, -1], [0] and [1, -1, 0].
Constraints
1 <= len(nums) <= 10**4- Elements may be negative, so a sliding window does not work here.
- Aim for O(n) time.
Goals
- Rewrite 'subarray sum equals k' as 'two prefix sums differ by k'
- Count earlier prefix sums with a dictionary instead of looping over them
- Seed the count with prefix 0 so subarrays starting at index 0 are included