Count the stretches of numbers that add up to k, negatives included. Keep a running total and a tally of totals seen, and look up the one that's k behind.
▼The problem
LeetCode 560 (Medium). Given an integer array nums (values can be negative or zero) and an integer k, return how many contiguous subarrays sum to exactly k.
Example: nums = [1, 2, -2, 1, 1, 1], k = 3 → **4**: [1, 2], [1, 2, -2, 1, 1], [2, -2, 1, 1, 1] and [1, 1, 1].
The solution
def subarray_sum(nums, k):
count = {0: 1} # altitude -> visits
total = answer = 0
for x in nums:
total += x
answer += count.get(total - k, 0)
count[total] = count.get(total, 0) + 1
return answerTranscript
Subarray Sum Equals K. Given a list of numbers, some negative, and a target k, count the stretches of neighbors that sum to exactly k.
Take one, two, minus two, one, one, one, and k equals three. Four stretches work: one, two at the start, the last three ones, and two longer ones across the minus two.
A sliding window fails. Growing it over a negative shrinks the sum, so you never know which way to move. Checking every stretch works, but that's n squared.
Think of a hike. Each number is a step up or down; your altitude is the running total. A stretch adds to k exactly when today's altitude is k above an earlier one. So at each step, ask: how often have I stood at altitude minus k?
In code, keep a logbook: a hash map from altitude to visits, starting with zero, seen once. For each number, add it to the total, add the count for total minus k to the answer, then log the total.
Let's hike. Up one, to one. Up two, to three: zero is logged once: one stretch. Down two, back to one. Up to two: nothing at minus one. Up to three: zero again, two stretches. Up to four: we need one, seen twice. Two ropes at once, four in all.
One pass, constant work per step: linear time. The logbook holds up to n altitudes: linear space.
Log every altitude, and look back k. That's Subarray Sum Equals K.