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.

long long count_subarrays(const std::vector<long long>& values, long long target);

count_subarrays({1, 1, 1}, 2);   // 2

The count is returned as a long long, because a long run of zeros has \(n(n+1)/2\) slices.

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^6 \) 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.