2302. 统计得分小于 K 的子数组数目 滑动窗口 or 前缀和+二分

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

• 典型的滑动窗口之越短越合法的统计数目的问题，对于这个不定长滑动窗口问题，大家可以看我的另一篇博客不定长滑动窗口

• 在这里就不详细介绍滑动窗口方法的代码啦,模版题目来的

class Solution:def countSubarrays(self, nums: List[int], k: int) -> int:# 滑动窗口，越短越好的计数问题ans,tmp,left = 0,0,0n = len(nums)for right,c in enumerate(nums):tmp += c while tmp * (right - left + 1) >= k :tmp -= nums[left]left += 1ans += right - left + 1return ans

• 主要介绍如何使用这个前缀和+二分如何求解
• 首先这个前缀和的思路来源：由于需要求解子数组的和的问题，那么为了在o(n)时间复杂度之内求解出区间和，所以会用到这个前缀和
• 二分：这个二分就不是很好求解了，下面给出思路，我们逐个遍历nums[i],求解出以nums[i]结尾的满足的子数组的个数，那么最长的情况就是从下标0到nums[i]的位置，我们只需使用check函数进行判断，然后二分即可

# 前缀和+ 二分n = len(nums)pre = [0]*(n+1)for i in range(n):pre[i+1] = pre[i] + nums[i]print(pre)def check(mid,right):tmp = (right-mid+1)*(pre[right+1] - pre[mid])return tmp < k # 二分检验ans = 0# 枚举以每一个元素作为结尾for right,c in enumerate(nums):l,r = 0,right res = 0 while l<=r:mid = (l+r) // 2 if check(mid,right):res = max(res,right-mid+1)r = mid - 1else:l = mid + 1ans += res return ans

思考

• 其实前缀和+二分感觉就是滑动窗口的重复情况，因为滑动窗口不会重新移动左边界变小，而是在不断向右变大右窗口，相比之下，前缀和+二分会每次都设置做窗口的最小值为0，虽然二分的时间复杂度只有o(logn),但是也是重复计算了，不过我们可以学习这种二分的方法！