class Solution {
public:
int numOfSubarrays(vector<int>& arr, int k, int threshold) {
}
};
1343. 大小为 K 且平均值大于等于阈值的子数组数目
给你一个整数数组 arr 和两个整数 k 和 threshold 。
请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。
示例 1：
输入：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 的值)。
示例 2：
输入：arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5 输出：6 解释：前 6 个长度为 3 的子数组平均值都大于 5 。注意平均值不是整数。
提示：
1 <= arr.length <= 1051 <= arr[i] <= 1041 <= k <= arr.length0 <= threshold <= 104原站题解
javascript 解法, 执行用时: 76 ms, 内存消耗: 51.1 MB, 提交时间: 2022-12-09 16:05:12
/**
* @param {number[]} arr
* @param {number} k
* @param {number} threshold
* @return {number}
*/
var numOfSubarrays = function(arr, k, threshold) {
var m = {};
let count = 0;
let sum = 0;
var t = threshold*k;
for(var i = 0; i < k-1;i++){
sum += arr[i];
m[i]= sum;
}
for(var i = k-1; i < arr.length; i++){
sum += arr[i];
m[i] = sum;
if((i-k) in m) {
if(sum - m[i-k] >= t){
count++
}
} else {
if(sum >= t){
count++;
}
}
}
return count;
};
python3 解法, 执行用时: 100 ms, 内存消耗: 25 MB, 提交时间: 2022-12-09 16:04:04
class Solution:
def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
if len(arr) < k:
return 0
addRes = sum(arr[:k])
res = 0
target = k*threshold
if addRes >= target:
res += 1
for i in range(k,len(arr)):
addRes = addRes + arr[i] - arr[i-k]
if addRes >= target:
res += 1
return res
javascript 解法, 执行用时: 64 ms, 内存消耗: 47.7 MB, 提交时间: 2022-12-09 16:03:51
/**
* @param {number[]} arr
* @param {number} k
* @param {number} threshold
* @return {number}
*/
var numOfSubarrays = function(arr, k, threshold) {
let sums = 0; // 子数组的和
let nums = 0; // 最后返回值，即符合条件的子数组个数
let len = arr.length; // 数组的长度
let target = k * threshold; // 子数组的目标和，大于等于这个值就满足条件
// 判断边界条件, 数组的长度 < 给定的子数组的长度, 必然不符合
if (len < k) return 0;
// 初始子数组的和
for (let i = 0; i < k; i++) sums += arr[i];
// 如果初始子数组就满足条件，nums加1
if (sums >= target) nums++;
for (let i = k; i < len; i++) {
// 这两步是整个算法的关键
// 新子数组和计算，即老子数组的和减去老子数组的第一个index的值，再加上当前index的值
// 可以理解为长度为k的窗口往后移动一位
sums -= arr[i - k]; // i = 3, k = 3, 就是减去arr[0]
sums += arr[i]; // 再加上arr[3]
if (sums >= target) nums++;
}
return nums;
};
java 解法, 执行用时: 1 ms, 内存消耗: 51.8 MB, 提交时间: 2022-12-09 16:02:18
/**
* step1 ： 取出前k个数求和，然后减去k*threshold ，如果结果大于0，说明符合要求。
* step2 ： 指针后移一位，用后移一位的值减去移动之前的第一位的值，再加上上次减法的结果，如果大于0，说明符合要求
**/
class Solution {
public static int numOfSubarrays(int[] arr, int k, int threshold) {
int sum = 0 ,result=0;
int sumTarget = k*threshold;
for (int i = 0; i < k; i++) {
sum += arr[i];
}
int adder = sum - sumTarget;
if (adder >= 0) {
result++;
}
int pos = k;
for (int i = 0; i < arr.length-k; i++) {
adder = adder+arr[pos]-arr[i];
if (adder>=0){
result++;
}
pos++;
}
return result;
}
}
cpp 解法, 执行用时: 72 ms, 内存消耗: 53.9 MB, 提交时间: 2022-12-09 16:00:52
// 滑动窗口，设置双指针i和j依次遍历
class Solution {
public:
int numOfSubarrays(vector<int>& arr, int k, int threshold) {
int res = 0;
for(int i=0,j=0,s=0;i<arr.size();i++){
s += arr[i];
if(i-j >= k) s -= arr[j++];
if(i-j+1 == k && s>=k*threshold) res++;
}
return res;
}
};