Subarray Sum Equals K

Problem

Given an integer array nums and an integer k, count how many contiguous, non-empty subarrays have elements that sum to exactly k. Elements may be negative, zero, or positive.

• The array is non-empty and has at most 50,000 elements.
• Each element has magnitude at most 5,000, so every prefix sum fits in a 64-bit integer.
• k can be any value a prefix sum could take, including 0 and negatives.

Examples

• nums = [2, 4, 2, 2, 4], k = 6 → 3. [2,4] at positions 0-1, [4,2] at 1-2, and [2,4] at 3-4.
• nums = [5, -3, 3, 1], k = 5 → 2. [5] and [5,-3,3].
• nums = [4, -4, 0, 4], k = 0 → 4. [4,-4], [4,-4,0], [0], and [-4,0,4].

Hints

1. The sum of nums[i..j] is the difference of two prefix sums. Which two?
2. For a fixed right end j, you want to know how many earlier prefix sums equal P[j] - k.
3. Walk left to right maintaining a hash map from prefix-sum value to how many times it has occurred; seed it with {0: 1}.