IntermediateArrays & Strings
Prefix sums: any range sum in O(1)
Store running totals once. Then the sum of nums[i..j] is prefix[j+1] − prefix[i], no loop needed.
The idea
prefix[k] is the sum of the first k numbers. The sum of a range is the total up to its end minus the total before its start.
Combined with a hash map of prefix sums you've seen, it counts subarrays with a given sum in one pass: a subarray ending here sums to k when some earlier prefix equals current − k.
Worked example
nums = [3, 1, 4, 1, 5]
- prefix = [0, 3, 4, 8, 9, 14]
- sum of nums[1..3] (1 + 4 + 1) = prefix[4] − prefix[1] = 9 − 3 = 6
In code (Python)
def build_prefix(nums):
prefix = [0]
for x in nums:
prefix.append(prefix[-1] + x)
return prefix
def count_subarrays_with_sum(nums, k):
seen = {0: 1} # prefix sum -> how many times
total = count = 0
for x in nums:
total += x
count += seen.get(total - k, 0)
seen[total] = seen.get(total, 0) + 1
return countO(n) to build, O(1) per range query.
How to spot it
- Many range-sum questions, “subarray sum equals k”, “product except self” (same idea with products).
Common mistakes
- Forgetting the leading 0, which breaks ranges starting at index 0.
- In the counting version, adding the current prefix before looking up total − k.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →