Count how many subarrays have sums within an inclusive range.
Given an integer array nums and two integers lower and upper, count the number of subarrays whose sum lies in the inclusive range [lower, upper].
A subarray is a contiguous, non-empty segment of the array. The answer may be large, so return the total count as an integer.
A brute-force approach that checks every subarray is too slow for large inputs, so the intended solution should exploit prefix sums and an efficient counting strategy.
Input Format
- An integer array
nums - Two integers
lowerandupper
The task is to count all pairs of indices (i, j) with i < j such that the sum of nums[i...j-1] is in [lower, upper].
Output Format
- Return a single integer: the number of valid subarrays.
Constraints
1 <= nums.length- Subarray sums may exceed 32-bit integer range, so use 64-bit arithmetic where needed
- Count all valid non-empty subarrays
lower <= upper
Example 1
Input
nums = [-2, 5, -1], lower = -2, upper = 2
Output
3
Explanation
The valid subarrays are: [-2], [-2, 5, -1], and [-1].
Example 2
Input
nums = [0], lower = 0, upper = 0
Output
1
Explanation
The only subarray is [0], and its sum is within the range.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.