[LeetCode] 1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold 大小为 K

Given an array of integers arr and two integers k and threshold, return *the number of sub-arrays of size k and average greater than or equal to *threshold.

Example 1:

Input: arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4
Output: 3
Explanation: Sub-arrays [2,5,5],[5,5,5] and [5,5,8] have averages 4, 5 and 6 respectively. All other sub-arrays of size 3 have averages less than 4 (the threshold).

Example 2:

Input: arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
Output: 6
Explanation: The first 6 sub-arrays of size 3 have averages greater than 5. Note that averages are not integers.

Constraints:

• 1 <= arr.length <= 10^5
• 1 <= arr[i] <= 10^4
• 1 <= k <= arr.length
• 0 <= threshold <= 10^4

这道题给了一个正整数数组 arr，和两个参数k，threshold。说是让找出所有长度为k的子数组的个数，使得该子数组的平均值大于等于 threshold。子数组的平均值的计算方法即为子数组之和除以其长度，这里就是除以k。而求子数组之和的问题，博主下意识的就会想到建立累加和数组，这样可以快速求出任意长度的子数组之和。这里也可以用这种方法，建立累加和数组 sums，然后就是遍历所有的长度为k的子数组，然后通过 sums[i]-sums[i-k] 快速得到其数组之和。接下来就要进行比较了，这里博主没有使用除法，因为除法没有乘法高效，用k乘以 threshold 的结果进行比较也是一样的，若满足条件，则结果自增1即可，参见代码如下：

解法一：

class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        int res = 0, n = arr.size(), target = k * threshold;
        vector<int> sums(n + 1);
        for (int i = 1; i <= n; ++i) {
            sums[i] = sums[i - 1] + arr[i - 1];
        }
        for (int i = k; i <= n; ++i) {
            int sum = sums[i] - sums[i - k];
            if (sum >= target) ++res;
        }
        return res;
    }
};

由于这道题只关心长度为k的子数组，那么建立整个累加和数组就略显多余了，只要维护一个大小为k的窗口就能遍历所有长度为k的子数组了。这就是滑动窗口 Sliding Window 的思路，遍历数组，将当前数字加到 sum 中，若i大于等于k，说明此时窗口大小超过了k，需要把左边界 arr[i-k] 减去，然后把 sum 跟 target 进行比较，注意这里的i必须要大于等于 k-1，因为要保证窗口的大小正好是k，参见代码如下：

解法二：

class Solution {
public:
    int numOfSubarrays(vector<int>& arr, int k, int threshold) {
        int res = 0, n = arr.size(), sum = 0, target = k * threshold;
        for (int i = 0; i < n; ++i) {
            sum += arr[i];
            if (i >= k) sum -= arr[i - k];
            if (i >= k - 1 && sum >= target) ++res;
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1343

类似题目：

K Radius Subarray Averages

Count Subarrays With Median K

参考资料：

https://leetcode.com/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold

https://leetcode.com/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold/solutions/503786/c-short-solution/

https://leetcode.com/problems/number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold/solutions/502740/java-python-3-2-codes-prefix-sum-and-sliding-window-w-analysis/

LeetCode All in One 题目讲解汇总(持续更新中...)