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

这道题到底在问什么

输入

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

输出

3

输入

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

输出

1

输入

arr=[1,1,1,1,1,1,1,1], k=3, threshold=4

输出

0

最优解：一步一步想明白

1. 3记牢两句:平均值比较换成「窗口和 ≥ k×threshold」也就是 ≥ 12;窗口滑动时和只需加右端、减左端。下面每帧都在套这两句。
2. 4上面这排是 [2,2,2,2,5,5,5,8] 的 8 个数。开滑前先把阈值线定好:平均值要 ≥ 4,等价于长度 3 的窗口和要 ≥ 3 乘 4 也就是 ≥ 12。接下来从最左边装出第一个长度 3 的窗口,然后一格一格往右滑。
3. 5先放第 0 个数 2,窗口里现在只有它一个,窗口和 = 2。窗口还没装满 3 个,先不忙比。
4. 6再放第 1 个数 2,窗口和从 2 加到 4。还差一个数才装满。
5. 7再放第 2 个数 2,窗口和从 4 加到 6。到这第一个长度 3 的窗口 [2,2,2] 装满了。
6. 8第一个窗口 [2,2,2] 的和是 6,拿去跟阈值线 12 比:6 比 12 小,平均值不够 4,不计。已计数 0 个。
7. 9窗口往右滑一格。右边新进来一个数 arr[3] = 2,先把它加进窗口和,和从 6 涨到 8。这会儿窗口暂时盖了 4 个数,马上要把最左边那个吐出去。
8. 10把离开窗口的最左端 arr[0] = 2(标红的这个)从和里减掉,和从 8 落回 6。窗口又是规规矩矩的长度 3,覆盖第 1 到第 3 个。整个滑动只做了一加一减,没有重新求和。
9. 11这个窗口的和是 6,跟阈值线 12 比:6 比 12 小,平均值不到 4,跳过。已计数 0 个。
10. 12窗口往右滑一格。右边新进来一个数 arr[4] = 5,先把它加进窗口和,和从 6 涨到 11。这会儿窗口暂时盖了 4 个数,马上要把最左边那个吐出去。
11. 13把离开窗口的最左端 arr[1] = 2(标红的这个)从和里减掉,和从 11 落回 9。窗口又是规规矩矩的长度 3,覆盖第 2 到第 4 个。整个滑动只做了一加一减,没有重新求和。
12. 14这个窗口的和是 9,跟阈值线 12 比:9 比 12 小,平均值不到 4,跳过。已计数 0 个。
13. 15窗口往右滑一格。右边新进来一个数 arr[5] = 5,先把它加进窗口和,和从 9 涨到 14。这会儿窗口暂时盖了 4 个数,马上要把最左边那个吐出去。
14. 16把离开窗口的最左端 arr[2] = 2(标红的这个)从和里减掉,和从 14 落回 12。窗口又是规规矩矩的长度 3,覆盖第 3 到第 5 个。整个滑动只做了一加一减,没有重新求和。
15. 17这个窗口的和是 12,跟阈值线 12 比:12 比 12 大或相等,达标,计一个,这窗口涂绿。已计数 1 个。
16. 18窗口往右滑一格。右边新进来一个数 arr[6] = 5,先把它加进窗口和,和从 12 涨到 17。这会儿窗口暂时盖了 4 个数,马上要把最左边那个吐出去。
17. 19把离开窗口的最左端 arr[3] = 2(标红的这个)从和里减掉,和从 17 落回 15。窗口又是规规矩矩的长度 3,覆盖第 4 到第 6 个。整个滑动只做了一加一减,没有重新求和。
18. 20这个窗口的和是 15,跟阈值线 12 比:15 比 12 大或相等,达标,计一个,这窗口涂绿。已计数 2 个。
19. 21窗口往右滑一格。右边新进来一个数 arr[7] = 8,先把它加进窗口和,和从 15 涨到 23。这会儿窗口暂时盖了 4 个数,马上要把最左边那个吐出去。
20. 22把离开窗口的最左端 arr[4] = 5(标红的这个)从和里减掉,和从 23 落回 18。窗口又是规规矩矩的长度 3,覆盖第 5 到第 7 个。整个滑动只做了一加一减,没有重新求和。
21. 23这个窗口的和是 18,跟阈值线 12 比:18 比 12 大或相等,达标,计一个,这窗口涂绿。已计数 3 个。
22. 24窗口从左滑到右,一共 6 个长度 3 的窗口都比过了。达标的是 [2,5,5]、[5,5,5]、[5,5,8] 这三个,它们的和分别是 12、15、18,都不小于阈值线 12。所以平均值大于等于 4 的窗口有 3 个,跟开头说的答案对上了。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
        threshold *= k
        s = sum(arr[:k])
        ans = int(s >= threshold)
        for i in range(k, len(arr)):
            s += arr[i] - arr[i - k]
            ans += int(s >= threshold)
        return ans

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        threshold *= k;
        int s = accumulate(arr.begin(), arr.begin() + k, 0);
        int ans = s >= threshold;
        for (int i = k; i < arr.size(); ++i) {
            s += arr[i] - arr[i - k];
            ans += s >= threshold;
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int numOfSubarrays(int[] arr, int k, int threshold) {
        threshold *= k;
        int s = 0;
        for (int i = 0; i < k; ++i) {
            s += arr[i];
        }
        int ans = s >= threshold ? 1 : 0;
        for (int i = k; i < arr.length; ++i) {
            s += arr[i] - arr[i - k];
            ans += s >= threshold ? 1 : 0;
        }
        return ans;
    }
}

复杂度

面试官可能追问