Subarrays Summing To K
Problem
Given a list of integers and a target k, count how many contiguous stretches of the list add up to exactly k. Stretches that start or end at different positions count separately even when they hold the same values. Negative numbers are allowed, so sums do not grow steadily as the stretch widens.
Examples
Input: nums = [1, 2, 3, 1], k = 3
Output: 2
Why: the stretches 1,2 and 3 both total 3Input: nums = [2, -1, 2, -1], k = 1
Output: 3
Why: negatives let several different stretches land on the same totalInput: nums = [0, 0], k = 0
Output: 3
Why: edge case, each single zero counts and so does the pairHints
0 / 3
Trying every start and end works but rechecks the same sums repeatedly. Think about a quantity that describes the whole prefix up to each position.
If you know the running total at two positions, the stretch between them is just the difference. So the question becomes how often a particular earlier total has occurred.
Walk the list keeping a running total. At each step, look up how many earlier prefixes had a total equal to the current total minus k and add that count to the answer, then record the current total as one more occurrence. Seed the record with one occurrence of a total of zero so stretches starting at the front are counted.
Solution
The sum of a stretch equals the running total at its end minus the running total just before its start, so a stretch hits k exactly when an earlier prefix total equals the current total minus k. A map from prefix total to occurrence count answers that in constant time, and it must start with one occurrence of zero so stretches beginning at index zero are counted. Because negatives are allowed, sliding-window shrinking would be unsound, which is why the counting approach is used instead. Time is O(n) on average, and space is O(n) for the map.
def count_subarrays_with_sum(nums, k):
counts = {0: 1} # prefix total -> how often it occurred
running = 0
total = 0
for x in nums:
running += x
# any earlier prefix equal to running - k closes a valid stretch here
total += counts.get(running - k, 0)
counts[running] = counts.get(running, 0) + 1
return total
print(count_subarrays_with_sum([1, 2, 3, 1], 3)) # -> 2
print(count_subarrays_with_sum([2, -1, 2, -1], 1)) # -> 3
print(count_subarrays_with_sum([0, 0], 0)) # -> 3Stuck on the idea rather than the code? Prefix Sums covers it.