Medium

题目描述

给你一个整数数组 arr 和两个整数 k 和 threshold，请你返回长度为 k 且平均值大于或等于 threshold 的子数组数目。

示例 1：

输入：arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
输出：3
解释：子数组 [2,5,5], [5,5,5] 和 [5,5,8] 的平均值分别为 4, 5, 6。其他长度为 3 的子数组的平均值都小于 4 （阈值）。

示例 2：

输入：arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
输出：6
解释：前 6 个长度为 3 的子数组平均值都大于 5。注意平均值不是整数。

约束条件：

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 10^4
  • 1 <= k <= arr.length
  • 0 <= threshold <= 10^4

提示：

  • 从大小为 K 的窗口开始，测试其平均值是否大于阈值。
  • 保持窗口大小为 k，每次移动一个元素，直到覆盖整个数组。计算平均值大于或等于阈值的窗口数量。

解题思路

这是一道典型的滑动窗口问题。核心思路是维护一个固定大小为 k 的窗口，计算每个窗口内元素的平均值。

解题思路

方法一：滑动窗口（推荐）

关键观察：我们可以避免重复计算，通过维护窗口内元素的和来高效计算平均值。另外，为了避免浮点数运算，我们可以将条件 平均值 >= threshold 转换为 总和 >= threshold * k。

具体步骤：

  1. 首先计算第一个长度为 k 的子数组的和
  2. 使用滑动窗口技术，每次移动窗口时，减去离开窗口的元素，加上新进入窗口的元素
  3. 对每个窗口，检查总和是否大于等于 threshold * k
  4. 统计满足条件的窗口数量

方法二：暴力法

对每个可能的长度为 k 的子数组，计算其平均值并与阈值比较。时间复杂度为 O(n*k)，在数据量大时效率较低。

滑动窗口方法的优势在于时间复杂度仅为 O(n)，空间复杂度为 O(1)，是最优解法。

代码实现

class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        int n = arr.size();
        int target = threshold * k;
        int count = 0;
        
        // 计算第一个窗口的和
        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }
        
        // 检查第一个窗口
        if (windowSum >= target) {
            count++;
        }
        
        // 滑动窗口
        for (int i = k; i < n; i++) {
            windowSum = windowSum - arr[i - k] + arr[i];
            if (windowSum >= target) {
                count++;
            }
        }
        
        return count;
    }
};

class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        n = len(arr)
        target = threshold * k
        count = 0
        
        # 计算第一个窗口的和
        window_sum = sum(arr[:k])
        
        # 检查第一个窗口
        if window_sum >= target:
            count += 1
        
        # 滑动窗口
        for i in range(k, n):
            window_sum = window_sum - arr[i - k] + arr[i]
            if window_sum >= target:
                count += 1
        
        return count

public class Solution {
    public int NumOfSubarrays(int[] arr, int k, int threshold) {
        int n = arr.Length;
        int target = threshold * k;
        int count = 0;
        
        // 计算第一个窗口的和
        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }
        
        // 检查第一个窗口
        if (windowSum >= target) {
            count++;
        }
        
        // 滑动窗口
        for (int i = k; i < n; i++) {
            windowSum = windowSum - arr[i - k] + arr[i];
            if (windowSum >= target) {
                count++;
            }
        }
        
        return count;
    }
}

/**
 * @param {number[]} arr
 * @param {number} k
 * @param {number} threshold
 * @return {number}
 */
var numOfSubarrays = function(arr, k, threshold) {
    const n = arr.length;
    const target = threshold * k;
    let count = 0;
    
    // 计算第一个窗口的和
    let windowSum = 0;
    for (let i = 0; i < k; i++) {
        windowSum += arr[i];
    }
    
    // 检查第一个窗口
    if (windowSum >= target) {
        count++;
    }
    
    // 滑动窗口
    for (let i = k; i < n; i++) {
        windowSum = windowSum - arr[i - k] + arr[i];
        if (windowSum >= target) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度说明
滑动窗口O(n)O(1)n 是数组长度，只需遍历一次数组
暴力法O(n×k)O(1)每个子数组都需要 O(k) 时间计算和

相关题目