LEETCODE 1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold 解题思路分析

题目大意:

大小为 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 = [1,1,1,1,1], k = 1, threshold = 0
输出:5

示例 3:

输入:arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5
输出:6
解释:前 6 个长度为 3 的子数组平均值都大于 5 。注意平均值不是整数。

示例 4:

输入:arr = [7,7,7,7,7,7,7], k = 7, threshold = 7
输出:1

示例 5:

输入:arr = [4,4,4,4], k = 4, threshold = 1
输出:1

提示:

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1343

解题思路分析:

本题如果暴力求每个长度为k的子数组和的话,时间会超时,因此我们可以使用滑动区间来解题。首先求出前k个元素的和(0到k-1区间),查看该和是否大于等于k*threshold。如果是,则结果加一。接下来,我们将区间向右移动一格(1到k区间),移动后,实际上是将第0个元素移除出区间,并且将第k个元素移进区间,这时区间和实际上是原区间和减去第0个元素再加上第k个元素而已。区间和改变后,查看其是否大于等于 k*threshold。接下来继续移动区间至 2到k+1区间,直到移动到数组末尾为止。这样能够快速的统计出所有符合条件的区间。

实现代码:

public int numOfSubarrays(int[] arr, int k, int threshold) {
    int sum = 0; // 区间和
    // 计算前k个元素区间和
    for(int i=0;i<k;i++) sum+=arr[i];
    // 满足条件的最小区间和
    int minSum = k * threshold;
    // 返回结果
    int res=0;
    // 如果区间和大于最小区间和,结果加一
    if(sum>=minSum) res++;
    // 不断向右移动区间
    int left=0,right=left+k;
    while(right<arr.length){
        sum-=arr[left];
        sum+=arr[right];
        if(sum>=minSum) res++;
        left++;
        right++;
    }
    return res;
}

本题解法执行时间为2ms。

Runtime: 2 ms, faster than 97.95% of Java online submissions for Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold.

Memory Usage: 56.7 MB, less than 100.00% of Java online submissions for Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1343-number-of-sub-arrays-of-size-k-and-average-greater-than-or-equal-to-threshold-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。