Subarray Sum Patterns
Count subarrays with a given sum in one pass: each prefix looks up how often prefix - k occurred before.
Prefix Sum and Kadane: Count subarrays summing to 7
i = 0: prefix becomes 3, so a subarray ending here sums to 7 if an earlier prefix was 3 - 7 = -4. Never seen, so none ends here. Then record prefix 3.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(n)
Before this
Related
Taught by the same lesson
Prefix Sum and Kadane covers these too, in the same run.