K-Sum Subarrays

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

The array may contain negative numbers, positive numbers, and zeros.

Example 1

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

Example 2

Input: nums = [1, 2, 3], k = 3
Output: 2
Explanation: [1, 2] sums to 3, and [3] sums to 3.

Example 3

Input: nums = [1, -1, 0], k = 0
Output: 3
Explanation: [1, -1], [0], and [1, -1, 0] all sum to 0.

Constraints

• 1 <= len(nums) <= 2 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7

Your solution should run faster than the O(n^2) brute force of checking every subarray directly.