Subarray Sum Equals K

Count continuous subarrays whose sum equals the target.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Subarray Sum Equals K: Count earlier prefix sums equal to current prefix minus target.

Input and goalCount continuous subarrays whose sum equals the target.

Seed the empty prefixFor nums = [1, -1, 1, -1, 1] and target 0, record prefix 0 once before scanning so subarrays starting at index 0 can match.

next i=010-1112-1314

mapLabelearlier prefix countsprefix0target0answer0

earlier prefix counts0count 1

Recognize it

The task counts contiguous ranges with an exact sum, values may be negative, and many ranges can end at the same index, so a monotone sliding window is unsafe.

Keep true

Before processing nums[i], the map counts every prefix ending before i. After prefix is updated, count(prefix - target) is exactly the number of valid subarrays ending at i; only then is the current prefix inserted.

Reuse it

Rewrite a range equation as current prefix minus earlier prefix. Store counts when duplicate earlier states represent distinct starts; this also transfers to subarray sums divisible by k and equal-count prefix signatures.

Pattern: Prefix sum plus hash map.

Simple idea: If the current prefix sum is p, a wanted subarray starts after an earlier prefix sum of p - target. Store how many times each earlier prefix sum appeared.

This is Two Sum on prefix sums.

def subarray_sum(nums: list[int], target: int) -> int:
   prefix_count = {0: 1}
   prefix = 0
   answer = 0

   for num in nums:
      prefix += num
      answer += prefix_count.get(prefix - target, 0)
      prefix_count[prefix] = prefix_count.get(prefix, 0) + 1

   return answer

Cost: $O(n)$ time and $O(n)$ space.

Why the map starts with {0: 1}: A prefix that already equals the target forms a valid subarray starting at index 0.