题目描述
思路解析动画文字版
记牢两句:平均值比较换成「窗口和 ≥ k×threshold」也就是 ≥ 12;窗口滑动时和只需加右端、减左端。下面每帧都在套这两句。
总览 · 先把阈值线乘出来,窗口从最左边装起：上面这排是 [2,2,2,2,5,5,5,8] 的 8 个数。开滑前先把阈值线定好:平均值要 ≥ 4,等价于长度 3 的窗口和要 ≥ 3 乘 4 也就是 ≥ 12。接下来从最左边装出第一个长度 3 的窗口,然后一格一格往右滑。
装入第 0 个 · 2：先放第 0 个数 2,窗口里现在只有它一个,窗口和 = 2。窗口还没装满 3 个,先不忙比。
装入第 1 个 · 2：再放第 1 个数 2,窗口和从 2 加到 4。还差一个数才装满。
装入第 2 个 · 2：再放第 2 个数 2,窗口和从 4 加到 6。到这第一个长度 3 的窗口 [2,2,2] 装满了。
比一比 · 窗口 [0,2] 和 = 6：第一个窗口 [2,2,2] 的和是 6,拿去跟阈值线 12 比:6 比 12 小,平均值不够 4,不计。已计数 0 个。
右端进 · arr[3] = 2：窗口往右滑一格。右边新进来一个数 arr[3] = 2,先把它加进窗口和,和从 6 涨到 8。这会儿窗口暂时盖了 4 个数,马上要把最左边那个吐出去。
左端出 · arr[0] = 2：把离开窗口的最左端 arr[0] = 2(标红的这个)从和里减掉,和从 8 落回 6。窗口又是规规矩矩的长度 3,覆盖第 1 到第 3 个。整个滑动只做了一加一减,没有重新求和。
比一比 · 窗口 [1,3] 和 = 6：这个窗口的和是 6,跟阈值线 12 比:6 比 12 小,平均值不到 4,跳过。已计数 0 个。
右端进 · arr[4] = 5：窗口往右滑一格。右边新进来一个数 arr[4] = 5,先把它加进窗口和,和从 6 涨到 11。这会儿窗口暂时盖了 4 个数,马上要把最左边那个吐出去。
左端出 · arr[1] = 2：把离开窗口的最左端 arr[1] = 2(标红的这个)从和里减掉,和从 11 落回 9。窗口又是规规矩矩的长度 3,覆盖第 2 到第 4 个。整个滑动只做了一加一减,没有重新求和。
比一比 · 窗口 [2,4] 和 = 9：这个窗口的和是 9,跟阈值线 12 比:9 比 12 小,平均值不到 4,跳过。已计数 0 个。
右端进 · arr[5] = 5：窗口往右滑一格。右边新进来一个数 arr[5] = 5,先把它加进窗口和,和从 9 涨到 14。这会儿窗口暂时盖了 4 个数,马上要把最左边那个吐出去。
左端出 · arr[2] = 2：把离开窗口的最左端 arr[2] = 2(标红的这个)从和里减掉,和从 14 落回 12。窗口又是规规矩矩的长度 3,覆盖第 3 到第 5 个。整个滑动只做了一加一减,没有重新求和。
比一比 · 窗口 [3,5] 和 = 12：这个窗口的和是 12,跟阈值线 12 比:12 比 12 大或相等,达标,计一个,这窗口涂绿。已计数 1 个。
右端进 · arr[6] = 5：窗口往右滑一格。右边新进来一个数 arr[6] = 5,先把它加进窗口和,和从 12 涨到 17。这会儿窗口暂时盖了 4 个数,马上要把最左边那个吐出去。
左端出 · arr[3] = 2：把离开窗口的最左端 arr[3] = 2(标红的这个)从和里减掉,和从 17 落回 15。窗口又是规规矩矩的长度 3,覆盖第 4 到第 6 个。整个滑动只做了一加一减,没有重新求和。
比一比 · 窗口 [4,6] 和 = 15：这个窗口的和是 15,跟阈值线 12 比:15 比 12 大或相等,达标,计一个,这窗口涂绿。已计数 2 个。
右端进 · arr[7] = 8：窗口往右滑一格。右边新进来一个数 arr[7] = 8,先把它加进窗口和,和从 15 涨到 23。这会儿窗口暂时盖了 4 个数,马上要把最左边那个吐出去。
左端出 · arr[4] = 5：把离开窗口的最左端 arr[4] = 5(标红的这个)从和里减掉,和从 23 落回 18。窗口又是规规矩矩的长度 3,覆盖第 5 到第 7 个。整个滑动只做了一加一减,没有重新求和。
比一比 · 窗口 [5,7] 和 = 18：这个窗口的和是 18,跟阈值线 12 比:18 比 12 大或相等,达标,计一个,这窗口涂绿。已计数 3 个。
完成 · 答案 3 个：窗口从左滑到右,一共 6 个长度 3 的窗口都比过了。达标的是 [2,5,5]、[5,5,5]、[5,5,8] 这三个,它们的和分别是 12、15、18,都不小于阈值线 12。所以平均值大于等于 4 的窗口有 3 个,跟开头说的答案对上了。
边界:k 比较大时窗口数量变少;k=1 时逐个元素比阈值;全部偏小则一个都不达标,答案 0。
面试重点:重叠窗口一加一减得 O(n)、乘 k 把比较变整数避开除法、窗口和不超 int 范围。
参考代码
from __future__ import annotationsfrom 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复杂度
- 时间：O(n)，n 为数组长度。求第一个窗口的和看 k 个数,之后每滑一步只做一次加、一次减、一次比较,每个元素总共进出窗口各一次,整体是线性扫描
- 空间：O(1)，自始至终只用了窗口和 s 与计数器 ans 两个整数,没有额外的数组或队列,峰值占用是常数,跟数组多长无关
易错点
面试追问把动画讲成自己的话
追问为什么定长窗口能做到 O(n),而不是每个窗口都求一遍和?
追问为什么把比较从「平均值 ≥ threshold」改成「窗口和 ≥ k×threshold」?
追问窗口和会不会溢出,这题的复杂度是多少?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
数组中的 k 个最强值
LeetCode 1471 · 中等 · 沿着 双指针套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题