416. Subarray Sum Equals K
You are given an integer array nums (values may be negative) and an integer k.
Count how many contiguous, non-empty subarrays of nums have elements that sum to exactly k. Two subarrays occupying different index ranges count separately even if their contents look identical.
Your function receives nums and k and returns a single integer: the number of such subarrays.
Example 1:
Input: nums = [1, 2, 1, 2, 1], k = 3
Output: 4
Explanation: Four windows hit 3: [1,2] at indices 0–1, [2,1] at 1–2, [1,2] at 2–3, and [2,1] at 3–4. Same contents, different positions — each counts.
Example 2:
Input: nums = [3, -1, 4, -2, 2], k = 2
Output: 3
Explanation: [3,-1] (indices 0–1), [4,-2] (2–3), and [2] (4–4) each total 2. Negative numbers mean sums can dip and recover, so windows can't be found by growing/shrinking alone.
Constraints:
- 1 ≤ nums.length ≤ 2 * 10⁴
- -1000 ≤ nums[i] ≤ 1000
- -10⁷ ≤ k ≤ 10⁷
Hints:
A sliding window fails here: negative values mean growing the window can shrink the sum, so the usual expand/contract logic has no direction to follow.
Let prefix[i] be the sum of the first i elements. A subarray (j..i) sums to k exactly when prefix[i+1] − prefix[j] = k — so while scanning, ask: how many earlier prefix sums equal (current prefix − k)? A hash map of prefix-sum frequencies answers in O(1). Seed it with {0: 1} so subarrays starting at index 0 are counted.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [1, 2, 1, 2, 1], k = 3
Expected output: 4