首页 > 其他分享 >[LeetCode] 1343. Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold

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

时间:2024-11-10 08:49:08浏览次数:1  
标签:arr Sub arrays Average than int threshold sum

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 <= 105
1 <= arr[i] <= 104
1 <= k <= arr.length
0 <= threshold <= 104

大小为 K 且平均值大于等于阈值的子数组数目。

给你一个整数数组 arr 和两个整数 k 和 threshold 。

请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。

思路

这道题是一道窗口尺寸固定的滑动窗口题。注意尽量不要在中间过程求平均值因为会涉及到精度问题。在过程中我们可以只求数字的 sum,不求平均值,到最后再计算平均值。

复杂度

时间O(n)
空间O(1)

代码

Java实现

class Solution {
    public int numOfSubarrays(int[] arr, int k, int threshold) {
        int n = arr.length;
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += arr[i];
        }

        int res = 0;
        if (sum >= threshold * k) {
            res++;
        }
        for (int i = k; i < n; i++) {
            sum += arr[i];
            sum -= arr[i - k];
            if (sum >= threshold * k) {
                res++;
            }
        }
        return res;
    }
}

标签:arr,Sub,arrays,Average,than,int,threshold,sum
From: https://www.cnblogs.com/cnoodle/p/18537603

相关文章

  • [LeetCode] 2841. Maximum Sum of Almost Unique Subarray
    Youaregivenanintegerarraynumsandtwopositiveintegersmandk.Returnthemaximumsumoutofallalmostuniquesubarraysoflengthkofnums.Ifnosuchsubarrayexists,return0.Asubarrayofnumsisalmostuniqueifitcontainsatleastmdisti......
  • 题解:AT_abc379_e [ABC379E] E - Sum of All Substrings
    很水的一道题。我们先把题目上各地的数字看成一个序列,然后考虑计算该序列分别会对答案的每一位产生多少贡献。具体的,我们从后往前考虑答案的每一位。通过简单推演可知,设你当前考虑到答案的第\(i\)个数字,那么原序列对这一位的贡献为\(\sum_{j=1}^{n-i+1}a_j\timesj\)。这个......
  • [USACO23JAN] Subtree Activation P 题解
    这种问题一看满足条件就知道,一般不用想着怎么模拟题意。考虑转化问题。假如节点\(u\)满足了条件一,也就是仅有子树节点全部开启。那么我们把转化具象为:进行\(\text{siz}_u\)次操作直接清空;进行\(\text{siz}_{\text{fa}(u)}-\text{siz}_u\)次操作使\(\text{fa}(u)\)满足......
  • SS241107B. 子序列们(sub)
    SS241107B.子序列们(sub)题意给你一个仅含有\(0,1\)的序列\(A\),定义序列\(B\)为每个元素是序列\(A\)的一个子序列的序列,满足第\(i\)个元素的长度是\(n-i+1\),且\(\forallj>i\),第\(j\)个元素是第\(i\)个元素的子序列。问有多少种本质不同的序列\(B\),对\(99824......
  • Understanding CAT ET Subscription for Work on 6NZ
    Ifyou’reconsideringusingCATCaterpillarET(ElectronicTechnician)forworkingonyour6NZengine,here’sabreakdownofhowthesubscriptionworksbasedondealerinformation: YearlySubscriptionModel-AnnualSubscription:CATEToperatesonayearl......
  • 在 Windows Server 2025 中,WSL2(Windows Subsystem for Linux 2)遇到无法使用镜像网络(mi
    在WindowsServer2025中,WSL2(WindowsSubsystemforLinux2)遇到无法使用镜像网络(mirrored)的问题,同时在使用virtioproxy模式时,子系统的IP与主机IP相同,可能是因为WSL2的网络配置与虚拟机的配置之间存在一些不匹配或不一致的设置。这里有几个可能的原因和解决方法:1. WSL......
  • averaged_perceptron_tagger_eng模块
    这里写自定义目录标题欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注......
  • Day25--arrays类
    Day25--arrays类Arrays类Arrays类是数组的工具类,位于java.util.Arrays。由于数组对象本身没有很多方法可供调用,API中提供了Arrays工具类以供使用,可对数组对象进行一些基本操作。Arrays类中的方法都是static修饰的静态方法,使用时可直接用类名调用(是“不用”而不是不......
  • E. Best Subsequence
    “最大权值闭合图,即给定一张有向图,每个点都有一个权值(可以为正或负或0),你需要选择一个权值和最大的子图,使得子图中每个点的后继都在子图中。”这样的定义可以让你理解算法执行的逻辑,却难以在你赛场上遇到它时牵动你的思绪更符合你做题时真切感受的描述应该是:给你一些点,消耗一些......
  • 2024.10.3 2022-2023 ICPC Brazil Subregional Programming Contest
    比赛链接Solved:12/14Rank:5/1k+Rank(vp):49/2k+Penalty:1619Dirt:45%前10个题都比较简单/套路。L做法很好想。但是……因为不会写启发式合并卡了40min,警钟长鸣!intsum[N];map<int,int>col[N];intsz[N];llnow[N],ans[N];voidmrg(intx,inty){x=find(x),y=fi......