Count Subarrays Summing to K
Implement countSubarraysSummingToK
Given an array of integers
nums (which may include negative values) and an integer k, return the total number of contiguous subarrays whose elements sum to exactly k. Overlapping subarrays all count separately.
Checking every subarray directly works, but it re-derives sums that share almost all of their elements with a sum already computed. A prefix sumPrefix SumThe running total of all elements from the start of the array up to a given index — prefix[i] = nums[0] + nums[1] + ... + nums[i]. The sum of any subarray nums[i..j] is just prefix[j] - prefix[i-1]. turns "does some subarray ending here sum to k" into "has an earlier prefix sum equal to (current prefix sum − k)" — a question a hashmap of prefix-sum frequencies can answer in O(1), letting the whole array be processed in a single pass.
Example 1:
Input: nums = [1,1,1], k = 2
Output: 2
Example 2:
Input: nums = [1,2,3], k = 3
Output: 2
Example 3:
Input: nums = [1,-1,0], k = 0
Output: 3
+ 8 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ nums.length ≤ 2 × 10⁴ - ●
-1000 ≤ nums[i] ≤ 1000 - ●
-10⁷ ≤ k ≤ 10⁷
nums =
[1, 1, 1]
k =
2