题目描述
给了一个数组，元素都是正的
给了数组分数的定义：子数组的和*数组长度
问分数严格小于k的非空子数组数目？
| f1-双指针 |
基本分析
- 能挖掘出啥性质？（1）数组都是正的，且另一个因子是长度相关，对每个右端点j，找到最远的左端点i时候，[i+1, j],[i+1,j]...[j, j]都是满足的，以j结尾的共计j-i+1个
- 双指针怎么实现？枚举右端点，记录当前和，找到最远的左端点，累加答案。
代码
class Solution:
def countSubarrays(self, nums: List[int], k: int) -> int:
ans = 0
s = 0
i = 0
n = len(nums)
for j in range(n):
s += nums[j]
while s * (j - i + 1) >= k:
s -= nums[i]
i += 1
ans += (j - i + 1)
return ans
总结
- 双指针的使用场景（1）连续；（2）有单调性，某个子数组满足，在该子数组内的更短的子数组也满足
- 这里枚举右端点，找左端点代码简单；枚举左端点，找右断电涉及边界问题，好像实现起来比较繁琐？