1 · Model, solve and test · 25 MIN

Count target-sum subarrays

Count target-sum subarrays

A subarray sum equals the difference between two prefix totals. While scanning, count how many earlier prefix totals equal current minus target. Include a zero prefix before reading any items so a matching subarray can start at index zero. Store frequencies rather than only membership because repeated prefix totals represent different starting positions. Negative numbers invalidate a simple shrinking-window approach, but the prefix-frequency method handles them naturally.

Count prior prefixes first, then record the current one.

Read the example

def solve(input):
    frequencies = {0: 1}
    prefix = answer = 0
    for value in input["values"]:
        prefix += value
        answer += frequencies.get(prefix - input["target"], 0)
        frequencies[prefix] = frequencies.get(prefix, 0) + 1
    return answer
import json
print(json.dumps(solve(json.loads("{\"values\":[1,1,1],\"target\":2}")), separators=(",", ":")))

2

Your challenge

Input is {values:list[int],target:int}. Return the number of nonempty contiguous subarrays whose sum equals target.

Solution cost: Expected O(n) dictionary operations; large integer bit costs are additional. time · O(n) distinct prefix frequencies. space

Common trap

Adding the current prefix before counting can incorrectly count an empty subarray for target zero.