Return the number of non-empty contiguous subarrays that sum to exactly target.
The array may contain negatives.
subarraySumCount(nums, target)
Input format: nums | target.
[1, 1, 1], target=2 // → 2
[1, 2, 3], target=3 // → 2 ([3] and [1,2])
[1, -1, 0], target=0 // → 3
A natural next step from existence: now count how many subarrays sum to target. The same prefix-sum idea applies, but a plain set only tracking "seen or not" isn't enough — a prefix sum value can occur multiple times, and each occurrence pairs with the current position as a distinct subarray.
A subarray ending at the current position sums to target exactly when some earlier prefix sum equals (current sum − target). Now the question is how many times that earlier value occurred — each occurrence is a different valid start point, so each counts separately.
Use a hash map from prefix-sum value to occurrence count instead of a set:
If the same prefix sum appears at three earlier positions, each pairs with the current position as a distinct subarray — different start points, same target sum — so all three must count, not just "this value occurred." Existence only needs to know a bucket is non-empty; counting needs to know how full it is.
Still a single O(n) pass with O(n) space, handling negatives for the same reason as the existence version — no reliance on monotonic sum behavior.
def subarray_sum_count(nums, target):
counts = {0: 1}
total = 0
result = 0
for n in nums:
total += n
result += counts.get(total - target, 0)
counts[total] = counts.get(total, 0) + 1
return result
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.