Medium · Prefix Frequency Map
Understand → Visualise → Practice.
Return the number of contiguous subarrays whose sum equals k.
A subarray from i + 1 to j sums to k exactly when prefix[j] − prefix[i] = k. Keep a count of the prefix sums seen so far.
counts = {0: 1}, for subarrays that start at index 0.
At each element, add counts[prefix − k] to the answer, then increment counts[prefix].
It counts every pair of prefixes differing by k.
O(n) time and O(n) space.
A sliding window only works with non-negative numbers; with negatives you need prefix counts.
Read the full guide first: Hash Maps and Hash Sets.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.