Subarray Sum Equals K
Problem
Count the contiguous non-empty subarrays whose elements add up to exactly k. Values may be negative, so a simple sliding window does not work.
Examples
Constraints
- • 1 <= nums.length <= 2 * 10^4
- • -1000 <= nums[i] <= 1000
- • -10^7 <= k <= 10^7
Hints & approach
Hint 1
A subarray sum is the difference of two prefix sums.
Hint 2
For the current prefix sum P, how many earlier prefix sums equal P - k?
Hint 3
Keep a hash map counting prefix sums seen so far, starting with {0: 1}.
Approachtry the hints first
Walk the array keeping a running prefix sum P and a hash map counting how many times each prefix sum has occurred, seeded with {0: 1} for the empty prefix. At each element, every earlier prefix equal to P - k marks the start of a subarray ending here with sum k, so add count[P - k] to the answer. Then increment count[P]. This handles negative numbers because it never relies on monotonic sums.
Time O(n) · Space O(n)