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

大小为 K 且平均值大于等于阈值的子数组数目

image.png

思路

又是一道数组题,仔细一看,还是我们熟悉的子数组问题,这里需要特别注意,凡是涉及到“子”的问题,务必注意是否是连续的!!!我曾多次在这里摔跟头。铜鼓观察给出的样例,应该是连续的,如果是不连续的,这个题我不会。

连续的就很好做了

用两个数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

`

评论

暂无评论