Prefix Sums

sum(i..j) = prefix[j] - prefix[i]

A prefix sum array stores running totals, so any subarray sum is a difference of two prefixes. Combined with a hash map counting earlier prefixes, "how many subarrays sum to k" becomes one pass: at each position, count earlier prefixes equal to prefix - k. Unlike a sliding window, this works with negative numbers. Two-dimensional prefix sums answer rectangle-sum queries in grids.

Counting subarrays that sum to k, run

I ran this with Python 3.12.3 (standard library only). Three test cases, including one with negative numbers where a sliding window would fail; the empty prefix (0 seen once) counts subarrays starting at index 0.

# Count subarrays summing to k with prefix sums + a hash map: O(n)
from collections import defaultdict

def subarray_sum(nums, k):
    count, prefix = 0, 0
    seen = defaultdict(int)
    seen[0] = 1                          # empty prefix
    for x in nums:
        prefix += x
        count += seen[prefix - k]        # earlier prefixes that make a sum of k
        seen[prefix] += 1
    return count

print(subarray_sum([1, 1, 1], 2))            # [1,1] twice
print(subarray_sum([1, 2, 3], 3))            # [1,2] and [3]
print(subarray_sum([3, -1, 1, 2, -2, 3], 3)) # negatives are fine

Output:

2
2
7

Seed the map with prefix 0

Forgetting seen[0] = 1 misses subarrays that start at the beginning.

त्वरित जाँच: Why use prefix sums instead of a sliding window for "subarray sum equals k"?

• They use no memory
• They work even when the array contains negative numbers
• They sort the array
• They are always O(1) overall