mediumPrefix sumsHash maps and sets target 25 min
Subarrays that sum to k
You get a list of integers nums and an integer k. A subarray is a run of one or more items that sit next to each other in the list, such as nums[1:4] (positions 1, 2 and 3). Return how many subarrays add up to exactly k.
Two subarrays count separately when they start or end at different positions, even if they hold the same values. The numbers can be negative or zero.
Example 1
Input
nums = [3, 1, 2, 4], k = 3Output2[3] at position 0, and [1, 2] at positions 1 and 2.
Example 2
Input
nums = [1, -1, 1, -1], k = 0Output4[1, -1] at positions 0 to 1, [-1, 1] at 1 to 2, [1, -1] at 2 to 3, and the whole list.
Constraints
1 ≤ len(nums) ≤ 20,000
-1,000 ≤ nums[i] ≤ 1,000
-107 ≤ k ≤ 107
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.
Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.