You are given a list of integers nums and an integer k. Return how many non-empty subarrays
(contiguous runs of positions) of nums add up to exactly k.
The numbers can be negative, so adding a number to a run can make its sum go down as well as up. Runs at different positions count separately, even when they hold the same numbers.
Example 1
- Input
- nums = [2, -1, 1, 3, -2], k = 3
- Output
- 3
[3], [-1, 1, 3] and the whole list each add up to 3.Example 2
- Input
- nums = [0, 0, 0], k = 0
- Output
- 6
Constraints
numsholds 1 to 2 × 10⁴ numbers.- Every number is between −1000 and 1000.
kis between −10⁷ and 10⁷.
Show the pattern
Prefix sums, Hashing
A run's sum is the difference of two running totals, so "runs ending here that sum to k" becomes "earlier running totals equal to this total minus k", which a hash map of counts answers at once.
See prefix sums in a visualiserShow the approach
Let total be the sum of the numbers so far. A run that ends at the current position adds up to
k exactly when the running total just before the run began was total − k. So walk through
nums once with a hash map seen from each running total to how many times it has occurred,
starting with {0: 1} for the empty start. At each number, add it to total, add
seen[total − k] (0 if missing) to the count, then record total in seen.
Time: O(n) · Space: O(n)