Subarray Sum Equals K

Statement

Given an integer array nums and an integer k, return the number of contiguous non-empty subarrays whose elements sum to exactly k.

Examples

nums = [1, 1, 1], k = 2
→ 2     (the subarrays [1,1] starting at index 0 and at index 1)

nums = [1, 2, 3], k = 3
→ 2     ([1,2] and [3])

nums = [1, -1, 0], k = 0
→ 3     ([1,-1], [-1,0,…wait], and [0]) - count carefully; the answer is 3

Constraints

• 1 ≤ len(nums) ≤ 2 × 10⁴
• -1000 ≤ nums[i] ≤ 1000
• -10⁷ ≤ k ≤ 10⁷
• Subarrays must be contiguous and non-empty. Order matters: [1,2] and [2,1] count separately if they appear at different positions.

What this problem is really testing

The naive O(n²) is straightforward: for each pair (l, r), sum the slice and compare. The interesting question is how to recognise that the problem is a seen-so-far shape. Once you reframe "subarray sums to k" as "two prefix sums differ by k", the hash-map solution drops out, and the algorithm becomes O(n), the same shape as Two Sum applied to prefix sums instead of values. The interviewer is checking whether you can move from "compute the sum" to "compare two values that differ by k".