210. Range Sums in Bounds
A shop records its daily profit (which may be negative) in the array nums. A stretch is any run of consecutive days, from day i to day j with i <= j, and its total is the sum of the profits on those days.
Count the stretches whose total lies between lower and upper, both included. Two stretches are different when their start day or end day differs, even if their totals are equal. The array can hold up to 40,000 days, so checking every stretch one by one is too slow.
Example 1
- Input:
- nums = [3,-4,2,1], lower = 0, upper = 3
- Output:
- 6
- Explanation:
The stretch totals in range are 3 ([3]), 1 ([3,-4,2]), 2 ([3,-4,2,1]), 2 ([2]), 3 ([2,1]) and 1 ([1]): 6 stretches.
Example 2
- Input:
- nums = [5], lower = 6, upper = 9
- Output:
- 0
- Explanation:
The only stretch has total 5, which is below the lower bound.
Example 3
- Input:
- nums = [0,0,0], lower = 0, upper = 0
- Output:
- 6
- Explanation:
All 6 stretches of three zeros have total 0.
Constraints
1 ≤ nums.length ≤ 4 × 104
-109 ≤ nums[i] ≤ 109
-109 ≤ lower ≤ upper ≤ 109
Stretch totals can exceed 32 bits, so use 64-bit sums.
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 3,200 msC++ 800 msJava 1,600 msJavaScript 1,600 msTypeScript 1,600 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)