双指针/滑动窗口问题

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

难度困难12

一个数字的 分数 定义为数组织和 乘以 数组的长度。

• 比方说，[1, 2, 3, 4, 5] 的分数为 (1 + 2 + 3 + 4 + 5) * 5 = 75 。

给你一个正整数数组 nums 和一个整数 k ，请你返回 nums 中分数 严格小于 k 的 非空整数子数组数目。

子数组 是数组中的一个连续元素序列。

timeout代码：

从nums的第1个元素开始，遍历到最后一个元素，用变量L表示。

进入while循环，从L开始，逐渐递增1个数量，计算该区间nums的和，如果满足条件，ans+1，否则退出while，L=L+1继续循环

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        n=len(nums)
        if n==1:
            return 1 if nums[0]<k else 0
        ans=0
        L=0
        while(L<n):
            i=1
            while(L+i<=n and sum(nums[L:L+i])*i<k):
                ans+=1
                i+=1
            L+=1
        return ans

双指针/滑动窗口优化代码：

子序列以右边结束位置为标志，从0遍历nums数组。如果满足条件ans加上左右的间隔数，否则，将left标志向右移动，用来减少求和。

right是子序列结束的位置，left是子序列开始的位置，中间的间隔是该条件下可以组成的子序列数目。

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        ans=he=left=0
        for right, num in enumerate(nums):
            he+=num
            while(he*(right-left+1)>=k):
                he-=nums[left]
                left+=1
            ans+=right-left+1
        return ans