题目:
给你一个整数数组 arr 和两个整数 k 和 threshold 。
请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。
示例:
输入: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 的值)。
解题方法:
滑窗法:
- 计算第一个长度为k子数组元素总和sum,判断是否满足大于k*threshold;
- 滑窗更新子数组:sum+=arr[i]-arr[i-k],判断新的sum是否满足大于k*threshold。
代码和结果:
class Solution {
public:
int numOfSubarrays(vector<int>& arr, int k, int threshold) {
int th=threshold*k;
int cnt=0;
int smv=0;
int len=arr.size();
int i;
for(i=0;i<k;i++)
smv+=arr[i];
if(smv>=th)
cnt++;
for(i=k;i<len;i++)
{
smv+=arr[i]-arr[i-k];
if(smv>=th)
cnt++;
}
return cnt;
}
};
运行结果:简单题已经做的七七八八了,这是我进军中等题的第一道题,感觉难度也还可以,要继续坚持下去,加油!