Count the contiguous subarrays whose sum is exactly k. The numbers can be negative, so a sliding window will not work.
DSA Animator › DSA Revision › Arrays › Subarray Sum Equals K
Remember: a subarray sum is a difference of two prefix sums. Count earlier prefixes equal to sum minus k with a hash map. The video solves Subarray Sum Equals K (LeetCode 560, Medium) with the Prefix Sum + Hash Map pattern from the Arrays topic, and you can replay every step in the interactive Subarray Sum Equals K animation.
Count the contiguous subarrays whose sum is exactly k. The numbers can be negative, so a sliding window will not work.
For 1, 2, 1, 2, 1 with k equal to 3, there are four: 1 2, 2 1, 1 2 and 2 1.
Checking every subarray is O of n squared. And with negatives, growing or shrinking a window tells you nothing.
Use prefix sums. If the running sum now is S, and some earlier prefix was S minus k, the part between them sums to k. So a hash map counts how often each prefix sum has appeared.
Start the map with prefix sum 0, seen once. Sum 1: we need minus 2, which is not there. Sum 3: we need 0, found once, so the count is 1. Sum 4: we need 1, found, so the count is 2. Sum 6: we need 3, found, so the count is 3. Sum 7: we need 4, found, so the count is 4. The answer is 4.
In code, put 0 in the map once. For each number, add it to the running sum. Add the count of sum minus k from the map, then record the current sum. That's O of n time and O of n space.
Remember: a subarray sum is a difference of two prefix sums. Count earlier prefixes equal to sum minus k with a hash map.