You get an integer array nums and an integer k. Count the subarrays whose numbers add up to exactly k.
A subarray is a run of one or more neighbouring elements. Two subarrays are different when they start or end at different positions, even if they hold the same numbers.
[3,4], [7] and [3,4,7,-7] each sum to 7. The last one shows why negative numbers matter: a run can overshoot k and come back down.
Positions 0–1, 1–2, 2–3, and the whole array, all sum to 0.
Constraints
1 <= nums.length <= 2 × 10⁴-1000 <= nums[i] <= 1000-10⁷ <= k <= 10⁷With negative numbers a sliding window can't work. Think in prefix sums instead: the run from i to j sums to prefix[j] − prefix[i − 1].
A run's sum is the difference of two running totals. Write running for the sum of everything from the start of nums up to some position. The run from position i to position j adds up to (total through j) minus (total just before i). So "this run sums to k" becomes "two running totals differ by exactly k".
Time O(n)Space O(n)
The full walkthrough and code are part of Premium
3