Count the number of contiguous subarrays whose sum equals k.
Build prefix sums on the fly and store their frequencies in a hash map. For each new prefix sum P, a subarray ending at the current index has sum k if some earlier prefix sum equalled P - k. Look that up in the map in O(1). One pass, O(n) time and space.
How to think about it
Recognise the pattern
The signal is “count subarrays with exact sum k” + array can contain negatives or zeros. When negative numbers are present, a sliding window breaks (you can’t predict whether growing or shrinking the window will increase the sum). Prefix sums with a hash map handle any integers and find exact sums in O(n).
Build the approach step by step
Brute force computes sum(nums[i:j+1]) for every pair. O(n²) or O(n³).
The prefix-sum insight:
Define prefix[i] = sum of nums[0..i-1] (with prefix[0] = 0). The sum of nums[i..j] is prefix[j+1] - prefix[i]. You want this to equal k, i.e. you want prefix[i] = prefix[j+1] - k.
So: as you scan and build the running prefix sum, at each step ask — “how many earlier prefix sums equal current_prefix - k?” That count is exactly the number of subarrays ending here whose sum is k.
Use a hash map count where count[p] = how many times prefix sum p has appeared so far. Initialise count[0] = 1 (the “empty prefix” before the array starts).
Walk through [1, 1, 1], k=2:
prefix=0 (initial): count={0:1}
i=0: prefix=1, look for 1-2=-1 → 0 matches. count={0:1, 1:1}
i=1: prefix=2, look for 2-2=0 → 1 match. count={0:1,1:1,2:1}
i=2: prefix=3, look for 3-2=1 → 1 match. count={0:1,1:1,2:1,3:1}
Total = 2 ✓ (subarrays [1,1] at indices 0-1 and 1-2)Complexity
- Time — O(n): one pass; each hash map lookup and insert is O(1) on average.
- Space — O(n): the hash map can hold up to n+1 distinct prefix sums.