大小为K且平均值大于等于阈值的子数组数目-滑动窗口

孙泽辉

发布于：2021年7月25日

字数：634字

时长：2分钟

次浏览

用到了滑动窗口

LeetCode题目链接：

1343. 大小为 K 且平均值大于等于阈值的子数组数目 - 力扣（LeetCode） (leetcode-cn.com)

给你一个整数数组 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 （threshold 的值)。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

因为是子数组，不是子序列（子序列不管顺序位置，子数组连续的），可以用滑动窗口

假装有个窗口，他只能装k个值，没有元素的时候往里填满k个，算一下平均值够不够threshold，够了就count++。

因为已经满了，就把开头的第一个元素删掉，继续装进来一个继续算。

这样就不用每次都取k个元素挨个算，代价小一点。

function solution(arr: number[], k: number, threshold: number) {
  let sum = 0,
    count = 0;
  // 先将前k个元素"填满"
  for (let i = 0; i <= k - 1; i++) {
    sum += arr[i];
  }
  // 看看最开始的k个元素符不符合条件
  if (sum / k >= threshold) {
    count++;
  }
  // 继续迭代后面的元素
  for (let i = k; i < arr.length; i++) {
    // 每次把开头的元素移出窗口
    sum -= arr[i - k];
    sum += arr[i];
    if (sum / k >= threshold) {
      count++;
    }
  }
  return count;
}

第一次写的有点简单，写到一个for循环里吧！

function solution(arr: number[], k: number, threshold: number) {
  let sum = 0,
    count = 0;

  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
    if (i >= k) {
      sum -= arr[i - k];
    }
    if (sum / k >= threshold && i >= k - 1) {
      count++;
    }
  }
  return count;
}

把第一次要干的都过滤出来了，看起来更加难以理解了点。。

函数式编程的话就不会有这个问题，一个循环干一件事，上面这样是函数式编程不推荐的。

参考资料：

• leetcode 1343. 大小为 K 且平均值大于等于阈值的子数组数目 #滑动窗口_哔哩哔哩_bilibili