说在前面
🎈每天进行一道算法题目练习,今天的题目是“统计得分小于 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 <= 10^5
1 <= nums[i] <= 10^5
1 <= k <= 10^15
思路分析
首先我们应该要先了解一下题意,结合题目描述和例子分析,我们可以得出以下几点:
- 1、子数组应该为连续的数组;
- 2、子数组的分数等于子数组元素和乘于子数组长度;
- 3、子数组的分数 严格小于 k。
这道题目的数据量为10^5,所以使用暴力枚举所有的子数组显然是不可以的,这道题目我们可以使用滑动窗口来进行解题。\
维护一个分数小于k的区间窗口及区间的分数,不断向右扩展,当区间分数大于k时,计算当前左端点可以组成的子数组数量并缩短区间,向前移动区间的左端点。
具体步骤如下:
- 1、向右扩展窗口区间
我们可以使用一重循环来遍历数组,遍历到的位置即为当前窗口区间的右端点。扩展的同时计算当前区间的分数,分数大于等于k时需要缩小窗口区间,即将左端点前移。
for(let i = 0; i < nums.length; i++){
sum += nums[i];
while(sum * (i - l + 1) >= k){
//左端点前移
}
}
- 2、向右缩小窗口区间
当分数大于等于k时需要缩小窗口区间,即将左端点前移,直到分数小于k时停止移动左端点,继续扩展右端点。
while(sum * (i - l + 1) >= k){
sum -= nums[l];
res += (i - l);
l++;
}
- 3、遍历完计算最后区间的子数组数量
遍历完之后我们还需要加上窗口区间的子数组数量。
while(nums.length - l > 0){
res += (nums.length - l);
l++;
}
AC代码
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var countSubarrays = function(nums, k) {
let l = 0;
let sum = 0,res = 0;
for(let i = 0; i < nums.length; i++){
sum += nums[i];
while(sum * (i - l + 1) >= k){
sum -= nums[l];
res += (i - l);
l++;
}
}
while(nums.length - l > 0){
res += (nums.length - l);
l++;
}
return res;
};
说在后面
🎉这里是 JYeontu,现在是一名前端工程师,有空会刷刷算法题,平时喜欢打打羽毛球🏸 ,平时也喜欢写些东西,既为自己记录📋,也希望可以对大家有那么一丢丢的帮助,写的不好望多多谅解🙇,写错的地方望指出,定会认真改进😊,在此谢谢大家的支持,我们下文再见🙌。