[Leetcode题解]大小为 K 且平均值大于等于阈值的子数组数目
文章目录
大小为 K 且平均值大于等于阈值的子数组数目

思路
又是一道数组题,仔细一看,还是我们熟悉的子数组问题,这里需要特别注意,凡是涉及到“子”的问题,务必注意是否是连续的!!!我曾多次在这里摔跟头。铜鼓观察给出的样例,应该是连续的,如果是不连续的,这个题我不会。
连续的就很好做了
用两个数left,right 维护一个区间,要求区间必须长度大于k.区间右界必须不超过数组的大小,即 right<n
`
# 区间不超过数组最右边
while r<n:
if 区间小了:
# do somethine
r+=1
elif 区间大了:
# do something
l+=1
else:
# do somehthing
l+=1 or l+=1 # 视情况而定
区间超过了,则右边界+1,区间不足则左边+1
假设区间长度刚好为k判断均值是否满足条件。
为了避免无重复的计算区间的和。我们使用一个前缀和数组sums保存到第i个元素的区间和。假设我们要求区间[l,r]的和那么只需要求
sums[l,r] = sums[r]-sums[l]+arr[l]
前缀和的代码如下可以参考,这是很基础但是很重要的,一定要闭着眼睛都能写出来。
`
# 求前缀和
sums = [0 for _ in range(len(arr))]
for index,num in enumerate(arr):
if index==0:
sums[index] = arr[0]
else:
sums[index] = sums[index-1]+arr[index]
`
完整代码如下:
`
class Solution(object):
def numOfSubarrays(self, arr, k, threshold):
"""
:type arr: List[int]
:type k: int
:type threshold: int
:rtype: int
"""
sums = [0 for _ in range(len(arr))]
for index,num in enumerate(arr):
if index==0:
sums[index] = arr[0]
else:
sums[index] = sums[index-1]+arr[index]
l, r = 0, 0
ans = 0
while r<len(arr):
if r-l+1<k:
r+=1
elif r-l+1>k:
l+=1
else:
if (sums[r]-sums[l]+arr[l])/k>=threshold:
ans+=1
r+=1
return ans
`

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论