Subarrays Summing to Target

Count the contiguous slices of a sequence of integers that sum to a target.

Slices are non-empty and counted by position, so the same contents at two different offsets count twice.

def count_subarrays(values: list[int], target: int) -> int: ...

count_subarrays([1, 1, 1], 2)   # 2

Examples

count_subarrays([3, 4, 7, 2, -3, 1, 4, 2], 7)   # 4
count_subarrays([0, 0, 0], 0)                    # 6

The zeros case is worth checking against your intuition: every pair of endpoints in a run of three zeros gives a slice summing to zero, and there are six of them.

Constraints

• Up to \( 2 \times 10^5 \) values, so the \( O(n^2) \) scan of every start against every end will not finish.
• Values may be negative and may be zero, and both matter. They rule out the sliding window: extending a window no longer moves the sum in one direction, so there is no direction to shrink towards.
• Everything is an exact integer count.