个人如何开网站公众号 网站开发

一、题目

给定数组，统计数组中长度为k的子数组且该子数组的平均值大于threshold的数量

二、思路

滑动窗思路，计算长度为k的滑动窗的平均值，关键点在于，每滑动一次，只需要去掉头增加尾，而不需要重新全部计算，进而将计算量从O(n*k)降低为O(n)

三、题解

class Solution:

    def numOfSubarrays(self,arr,k,threshold):

        curr = sum(arr[:k])

        n = len(arr)

        count = 1 if curr >= threshold*k else 0

        for i in range(k,n):

            curr += arr[i] - arr[i-k]

            count += 1 if curr >= threshold*k else 0

        return count