Count Subarrays With Score Less Than K
The score of an array is defined as the product of its sum and its length.
- For example, the score of
[1, 2, 3, 4, 5]is(1 + 2 + 3 + 4 + 5) * 5 = 75.
Given a positive integer array nums and an integer k, return the number of non-empty subarrays of nums whose score is strictly less than k.
A subarray is a contiguous sequence of elements within an array.
Example 1
Input
nums = [2,1,4,3,5], k = 10Output
6The 6 subarrays having scores less than 10 are [2], [1], [4], [3], [5], and [2,1]; subarrays such as [1,4] and [4,3,5] are not counted because their scores are not strictly less than 10.
Example 2
Input
nums = [1,1,1], k = 5Output
5Every subarray except [1,1,1] has a score less than 5, so there are 5 valid subarrays.
Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^5
- 1 <= k <= 10^15