LeetCode 6098. Count the number of subarrays whose score is less than K (prefix and + binary search)

List of articles

• 1. subject
• 2. Problem solving

1. subject

Of an array fraction Defined as an array of and multiply Array of length .

For example ,[1, 2, 3, 4, 5] The score of is (1 + 2 + 3 + 4 + 5) * 5 = 75 . Here's an array of positive integers nums And an integer k , Please return nums Middle score Strictly less than k Of Number of non empty integer subarrays .

Subarray Is a sequence of consecutive elements in an array .

 Example  1：
 Input ：nums = [2,1,4,3,5], k = 10
 Output ：6
 explain ：
 Yes  6  The score of the subarray is less than  10 ：
- [2]  The score is  2 * 1 = 2 .
- [1]  The score is  1 * 1 = 1 .
- [4]  The score is  4 * 1 = 4 .
- [3]  The score is  3 * 1 = 3 . 
- [5]  The score is  5 * 1 = 5 .
- [2,1]  The score is  (2 + 1) * 2 = 6 .
 Be careful , Subarray  [1,4]  and  [4,3,5]  Unqualified ,
 Because their scores are  10  and  36, But we need to find that the score of the subarray is strictly less than  10 .

 Example  2：
 Input ：nums = [1,1,1], k = 5
 Output ：5
 explain ：
 except  [1,1,1]  The score of each sub array is less than  5 .
[1,1,1]  The score is  (1 + 1 + 1) * 3 = 9 , Greater than  5 .
 So there are  5  The subarray score is less than  5 .
 
 Tips ：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5
1 <= k <= 10^15

Copy

source ： Power button （LeetCode） link ：https://leetcode.cn/problems/count-subarrays-with-score-less-than-k Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

2. Problem solving

• With each number nums[i] by Left endpoint Subarray , How many right endpoints satisfy the condition
• The total number of questions is positive ,sum*len It's monotonous , You can do a binary search , Find the rightmost position j, Meet the conditions sum[i: j]*(j-i+1) < k

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        n, prevsum = len(nums), [0]*len(nums)
        for i in range(n):
            prevsum[i] = (0 if i==0 else prevsum[i-1]) + nums[i]
        def partsum(prevsum, i, mid):
            return (prevsum[mid]-(0 if i==0 else prevsum[i-1]))*(mid-i+1)
        def bs(prevsum, i, r, k):
            l = i
            while l <= r:
                mid = (l+r)//2
                s = partsum(prevsum, i, mid)
                if s >= k:
                    r = mid-1
                else:
                    if mid==n-1 or partsum(prevsum, i, mid+1) >= k:
                        return mid-i+1
                    else:
                        l = mid+1
            return 0

        ans = 0
        for i in range(n):
            ans += bs(prevsum, i, n-1, k)
        return ans

Copy

6264 ms 26.8 MB Python3

---

my CSDN Blog address https://michael.blog.csdn.net/