2302. 统计得分小于 K 的子数组数目（Rating 1808）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

2302. 统计得分小于 K 的子数组数目

Rating 1808

思路

看到题目数据范围是 1e5，猜测大概率是个 O(n) 或者 O(nlogn) 的做法。

考虑固定子数组的右端点时，如何寻找左端点？

注意到子数组单调性，左端点越靠左，那么得分越高；反之则越低。

因此可以考虑二分：

遍历数组，将第 i 个位置当作右端点，然后利用单调性二分查找 [0, i] 之间的数作为子数组左端点，找到子数组得分严格小于 k 且左端点尽量靠左的位置即可。

为了每次二分时，快速计算出得分，这里需要提前维护一个前缀和，可以快速得到区间内的数字之和。

提交后虽然通过了，但是发现耗时比较高。

看了下之前提交通过的代码，发现之前自己用滑动窗口也通过了此题。

为啥本题可以用滑动窗口？

参考灵神的题解

• 连续子数组
• 有单调性

因此，以后对于满足以上2个条件的题目，可以先优先考虑一下滑动窗口是否可以解决，算法复杂度更低。

代码

二分法

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        prs = [0] * (n + 1) # 维护前缀和
        for i, num in enumerate(nums):
            prs[i + 1] = prs[i] + num
        ret = 0
        for i in range(n):
            lb, rb = 0, i # 二分[0, i]
            xb = -1 # 待找的左边界
            while lb <= rb:
                mid = (lb + rb) // 2
                s = (prs[i + 1] - prs[mid]) * (i - mid + 1)
                if s < k:
                    xb = mid
                    rb = mid - 1
                else:
                    lb = mid + 1
            if xb < 0: # 如果待找的左边界仍为默认值-1，说明以i为右端点的所有子数组都不满足严格，未找到
                continue
            ret += (i - xb + 1) # 将[xb, i]中间的子数组数量加入答案
        return ret    

滑动窗口

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        n, l, s, ret = len(nums), 0, 0, 0
        for r, num in enumerate(nums): # 遍历右端点，移动左端点
            s += num # 更新区间和
            while s * (r - l + 1) >= k: # 只要>=k就移动左端点
                s -= nums[l] # 更新区间和
                l += 1 # 移动左端点
            ret += r - l + 1 # 更新答案
        return ret