【每日一题】LeetCode 1343.大小为K且平均值大于等于阈值的子数组数目（数组、滑动窗口）

【每日一题】LeetCode 1343.大小为K且平均值大于等于阈值的子数组数目（数组、滑动窗口）

题目描述

给定一个整数数组 arr 和两个整数 k 和 threshold，要求找出数组中长度为 k 且平均值大于等于 threshold 的子数组的数量。

输入格式

• arr: 一个整数数组。
• 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]。

• 示例 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 * threshold，则说明这个窗口满足条件。然后，我们开始滑动窗口，每次向右移动一个元素，移除窗口最左边的元素，添加一个新的元素到窗口的右边。每次移动后，我们更新窗口的和，并检查是否满足条件。这个过程一直持续到窗口滑过数组的末尾。

输入示例

• arr = [2,2,2,2,5,5,5,8]
• k = 3
• threshold = 4

代码实现

class Solution {
    public int numOfSubarrays(int[] arr, int k, int threshold) {
        int n = arr.length; // 数组的长度
        int sum = 0, count = 0; // sum用于累计满足条件的子数组数量，count用于存储当前窗口的和

        // 初始化第一个窗口的和
        for (int i = 0; i < k; i++) {
            count += arr[i]; // 累加前k个元素的值
        }

        // 如果第一个窗口的和满足条件，增加计数
        if (count >= threshold * k) {
            sum++;
        }

        // 滑动窗口
        for (int i = k; i < n; i++) {
            count = count - arr[i - k] + arr[i]; // 移除窗口左侧的元素，加上右侧的元素
            if (count >= threshold * k) {
                sum++; // 如果当前窗口的和满足条件，增加计数
            }
        }

        return sum; // 返回满足条件的子数组数量
    }
}