Subarray Sum Equals K

The problem. Given an integer array nums and an integer k, return how many contiguous subarrays add up to exactly k. The numbers can be negative.

Example

Input:  nums = [1, 1, 1], k = 2
Output: 2      [1, 1] starting at index 0, and [1, 1] starting at index 1

Input:  nums = [1, 2, 3], k = 3
Output: 2      [1, 2] and [3]

Because values can be negative, adding an element can make a sum smaller — so the usual sliding window (grow while too small, shrink while too big) doesn't work here. We need a different way to avoid re-adding numbers.