Subarray Sum Equals K

Problem

Given an array of integers (which may include negatives) and a target sum k, return the number of contiguous subarrays whose elements sum to exactly k.

Example 1:

Input: nums = [2, -3, 3, 6, 2], k = 2
Output: 3
Explanation: [2] (index 0), [2, -3, 3] (indices 0-2), and [2] (index 4) all sum to 2.

Example 2:

Input: nums = [4, 6, -2, -3, 5], k = 6
Output: 2
Explanation: [6] (index 1) and [6, -2, -3, 5] (indices 1-4) sum to 6.

Example 3:

Input: nums = [3, -2, 5], k = 3
Output: 2
Explanation: [3] (index 0) and [-2, 5] (indices 1-2) both sum to 3.

Constraints:

• 1 <= nums.length <= 4 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7

Solution Breakdown

Approach - one pass with a running prefix and a hash map counting earlier prefix values.

The prefix algebra turns the problem into a lookup. Write the subarray condition as prefix[r+1] - prefix[l] = k, rearrange to prefix[l] = prefix[r+1] - k, and the question "how many subarrays ending at index r sum to k" becomes "how many earlier prefixes equal the current prefix minus k". A dict mapping prefix value to occurrence count answers that in O(1) per step, so the whole scan is O(n). No prefix array is needed - only the running value is ever consulted.

Two details make it correct. First, the dict is seeded with seen[0] = 1 - the empty prefix before index 0. Without it, a subarray that starts at the array's start (running prefix exactly k) finds nothing to match: on [3, -2, 5] with k=3, the prefix 3 must find the seed to count [3]. Second, the order inside the loop: add to total using the current prefix, and only then record it in seen. Storing first lets k = 0 match the current prefix against itself, counting a zero-length subarray.

Trace [2, -3, 3, 6, 2], k=2. Prefixes run 2, -1, 2, 8, 10; seed {0: 1}. At prefix 2 (index 0): look for 0 - found once (the seed), counting the stretch from the array's start to here: [2] (indices 0-0). Store 2: 1. At -1 (index 1): look for -3, none. At 2 again (index 2): look for 0 - the seed again, counting the stretch from the array's start to here: [2, -3, 3] (indices 0-2). Store 2: 2. At 8 (index 3): look for 6, none. At 10 (index 4): look for 8 - found once (the prefix after index 3), counting [2] (indices 4-4). Total: 3.

Edge cases - the seed {0: 1} counts subarrays starting at index 0; check-before-store keeps k = 0 from counting zero-length slices; a single element equal to k ([5], k=5) is counted by the seed alone: prefix 5 looks for 0.

Complexity - O(n) time, O(n) space worst case (all prefixes distinct). Sliding window cannot substitute when negatives are present because the shrink step needs monotone sums; the dict has no such requirement.