73. Stretches Summing to K
A bakery writes down its profit or loss for each day in the array nums; losses are negative and a break-even day is zero. The owner wants to know how many streaks of consecutive days add up to exactly the target k.
Return the number of non-empty contiguous subarrays of nums whose elements sum to k. Two subarrays are counted separately if they start or end at different positions, even if they contain the same values. The answer is guaranteed to fit in a 32-bit signed integer. Because values can be negative, a sliding window will not work directly.
Example 1
- Input:
- nums = [2,-1,3,1,-2,2], k = 3
- Output:
- 4
- Explanation:
The subarrays [3], [-1,3,1], [2,-1,3,1,-2] and [-1,3,1,-2,2] each sum to 3.
Example 2
- Input:
- nums = [1,1,1,1], k = 2
- Output:
- 3
- Explanation:
The three windows of length two each sum to 2.
Constraints
1 ≤ nums.length ≤ 106
-1000 ≤ nums[i] ≤ 1000
-109 ≤ k ≤ 109
The answer fits in a 32-bit signed integer.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)