题目描述
思路解析
一句话答案：LeetCode 1343 大小为 K 且平均值大于等于阈值的子数组数目用定长滑动窗口：维护长度 K 的窗口和，进一个数、出一个数，和 ≥ threshold×K 就计一个，避开重复求和。时间 O(n)、空间 O(1)。
长度必须正好 K、平均值还要够高，这题在数什么
给你数组 arr、窗口长度 K 和阈值 threshold，要数出这样的连续子数组：长度正好是 K，而且这一段所有数的平均值大于等于 threshold。连续就是数组里挨着的一段，不许跳着挑。题面 K 取 3、阈值 4 时答案是 3——长度 3 的连续段一共 6 个，其中三段平均值够到 4。
每个窗口都从头加 K 个数，重叠段白算
最直接的做法是把每一个长度 K 的窗口单独拎出来，里面 K 个数从头加一遍求和、再除以 K 跟阈值比。数组长 n 时窗口有 n−K+1 个，每个都要加 K 个数，加法总次数是窗口个数乘 K，规模到了 O(n×K)。可这些窗口彼此挨着、大段重叠，相邻两个只差最左和最右一个数，中间 K−1 个数被反复重加，白算了一大截。
相邻窗口只差两个数，和能不能接着上一次算
既然相邻窗口中间那段完全一样，就没必要每次从头求和。窗口往右滑一格，只有最右边多进来一个新数、最左边少掉一个旧数，中间纹丝不动。于是新窗口的和 = 旧窗口的和 + 右端新进的数 − 左端离开的数，一次加、一次减就更新完，跟窗口多长无关。这种固定长度往右挪、进一个出一个维护窗口和的做法，就是定长滑动窗口。
阈值线先乘出来，滑动时只加右端减左端
还有一步能省掉除法：判定平均值 ≥ threshold，两边同乘正数 K，等价于窗口和 ≥ K×threshold。先把阈值线 K×threshold 算好，往后每个窗口只拿和去跟它比，全程整数比较，既快又不碰浮点误差。流程是：先把前 K 个数求和当第一个窗口比一次；接着下标从 K 往右，每步给窗口和加上进来的数、减去离开的数，再比一次，达标就把计数加一。
题面那组数一格一格滑到底，数出 3
题面 arr=[2,2,2,2,5,5,5,8]，阈值线先定好：3×4 = 12，之后只跟 12 比。第一个窗口 [2,2,2] 和是 6，比 12 小，不计。往右滑一格，进 arr[3]、出 arr[0] 都是 2，和还是 6，跳过；再滑进 arr[4]=5、出 arr[1]=2，和 9，不够；再滑进 arr[5]=5、出 arr[2]=2，和到 12，够到阈值线，计一个；接着两步和分别是 15、18，各计一个。六个窗口的和依次是 6、6、9、12、15、18，达标的三个是 [2,5,5]、[5,5,5]、[5,5,8]，答案 3。
线性时间从哪来，哪几笔一反就把答案算歪
求第一个窗口的和看 K 个数，之后每滑一步只做一次加、一次减、一次比较，每个数只进窗口一次、出窗口一次，整体 O(n)。空间上只握着窗口和与计数器两个整数，没有额外数组，是常数 O(1)。
有几处一反就出错。真去算平均值、拿窗口和除以 K 再比，会掉进浮点精度坑，像 [11,13,17] 的平均值根本不是整数；先把阈值乘成 K×threshold、全程整数比较就绕开了。判定写成严格大于会漏掉平均值正好等于阈值的窗口，题面 [2,5,5] 平均值恰好 4，用 ≥ 才计得上、写成 ＞ 就丢了它。图省事每个窗口都把 K 个数重加一遍，复杂度立刻退回 O(n×K)，一加一减就白设计了。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢两句:平均值比较换成「窗口和 ≥ 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题