Prefix Sum + Hashmap

When To Use

Use this instead of sliding window when the array can contain negative numbers or the target condition is not monotonic.

Template

prefix = 0
freq[0] = 1
 
for x in nums:
    prefix += x
    ans += freq[prefix - target]
    freq[prefix]++

Problems Using This Pattern

Subarray Sum Equals K

Problem: count subarrays whose sum is exactly k.

Lookup: previous prefix prefix - k.

Continuous Subarray Sum

Problem: check if a length-at-least-2 subarray sum is divisible by k.

State: first index where each prefix % k appeared.

Contiguous Array

Problem: find the longest subarray with equal number of 0s and 1s.

Trick: treat 0 as -1, then find longest subarray with sum 0.

Maximum Size Subarray Sum Equals K

Problem: find the longest subarray whose sum is exactly k.

State: first index where each prefix sum appeared.