Subarray sum equals k
We'll cover the following
Count the contiguous subarrays whose sum is exactly k.
Watch it run
Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.
i-20
-11
12
13
-24
-35
-26
-37
-28
59
610
-311
-212
113
114
415
Running sum is -2. A subarray ending here sums to 5 if an earlier running sum was -7. Seen 0 times, so add 0.
sums {0:1, -2:1} · count 0
1 / 17
The idea
Complexity
| Time | Space | Why |
|---|---|---|
O(n) | O(n) | One pass; the map stores each prefix sum seen. |
In Python
def subarray_sum(nums, k):
seen, pre, count = {0: 1}, 0, 0
for x in nums:
pre += x
count += seen.get(pre - k, 0)
seen[pre] = seen.get(pre, 0) + 1
return countSummary: say it in the interview
- Keep a running total. A subarray ending here sums to k when the total minus k equals some earlier total. Store how many times each total has appeared.
- Time O(n), space O(n). One pass; the map stores each prefix sum seen.