2302.统计得分小于 K 的子数组数目:滑动窗口(不需要前缀和)
【LetMeFly】2302.统计得分小于 K 的子数组数目:滑动窗口(不需要前缀和)
力扣题目链接:https://leetcode.cn/problems/count-subarrays-with-score-less-than-k/
一个数组的 分数 定义为数组之和 乘以 数组的长度。
- 比方说,
[1, 2, 3, 4, 5]
的分数为(1 + 2 + 3 + 4 + 5) * 5 = 75
。
给你一个正整数数组 nums
和一个整数 k
,请你返回 nums
中分数 严格小于 k
的 非空整数子数组数目。
子数组 是数组中的一个连续元素序列。
示例 1:
输入:nums = [2,1,4,3,5], k = 10 输出:6 解释: 有 6 个子数组的分数小于 10 : - [2] 分数为 2 * 1 = 2 。 - [1] 分数为 1 * 1 = 1 。 - [4] 分数为 4 * 1 = 4 。 - [3] 分数为 3 * 1 = 3 。 - [5] 分数为 5 * 1 = 5 。 - [2,1] 分数为 (2 + 1) * 2 = 6 。 注意,子数组 [1,4] 和 [4,3,5] 不符合要求,因为它们的分数分别为 10 和 36,但我们要求子数组的分数严格小于 10 。
示例 2:
输入:nums = [1,1,1], k = 5 输出:5 解释: 除了 [1,1,1] 以外每个子数组分数都小于 5 。 [1,1,1] 分数为 (1 + 1 + 1) * 3 = 9 ,大于 5 。 所以总共有 5 个子数组得分小于 5 。
提示:
1 <= nums.length <= 105
1 <= nums[i] <= 105
1 <= k <= 1015
Hard里面的简单题。
解题方法:滑动窗口
本题计算的是字数组和乘以数组长度,由于数组元素为正,所以数组中元素越多计算得到的值越大,具有单调性,可以使用滑动窗口。
使用$cnt$记录窗口中元素总和,右指针依次遍历数组中每个元素作为窗口终点(遍历时将指向元素加入窗口)。
对于每个右指针的位置:
如果$cnt*len(subArray)\geq k$,则不断右移左指针。
左指针移动结束后所在位置就是第一个窗口“分数”小于“k”的位置,从左指针到右指针任一元素开始到右指针所指元素结束的子数组“分数”都小于“k”,都是合法子数组。总个数为$r-l+1$,累加到答案中即可。
- 时间复杂度$O(len(nums))$
- 空间复杂度$O(1)$
AC代码
C++
1 |
|
Python
1 |
|
Java
1 |
|
Go
1 |
|
同步发文于CSDN和我的个人博客,原创不易,转载经作者同意后请附上原文链接哦~
千篇源码题解已开源
2302.统计得分小于 K 的子数组数目:滑动窗口(不需要前缀和)
https://blog.letmefly.xyz/2025/04/30/LeetCode 2302.统计得分小于K的子数组数目/