1343. 大小为 K 且平均值大于等于阈值的子数组数目 #
- 标签:数组、滑动窗口
- 难度:中等
题目大意 #
描述:给定一个整数数组 arr
和两个整数 k
和 threshold
。
要求:返回长度为 k
且平均值大于等于 threshold
的子数组数目。
说明:
- $1 \le arr.length \le 10^5$。
- $1 \le arr[i] \le 10^4$。
- $1 \le k \le arr.length$。
- $0 \le threshold \le 10^4$。
示例:
|
|
解题思路 #
思路 1:滑动窗口(固定长度) #
这道题目是典型的固定窗口大小的滑动窗口题目。窗口大小为 k
。具体做法如下:
ans
用来维护答案数目。window_sum
用来维护窗口中元素的和。left
、right
都指向序列的第一个元素,即:left = 0
,right = 0
。- 向右移动
right
,先将k
个元素填入窗口中。 - 当窗口元素个数为
k
时,即:right - left + 1 >= k
时,判断窗口内的元素和平均值是否大于等于阈值threshold
。- 如果满足,则答案数目 + 1。
- 然后向右移动
left
,从而缩小窗口长度,即left += 1
,使得窗口大小始终保持为k
。
- 重复 3 ~ 4 步,直到
right
到达数组末尾。 - 最后输出答案数目。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n)$。
- 空间复杂度:$O(n)$。