当前位置：首页 > news >正文

LeetCode 2302 统计得分小于K的子数组数目（滑动窗口）

news 2025/4/30 11:46:12

先给出示例吧

输入：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 。

这还只是我优化后的思路，本来我是借助二维数组去维护其前缀和的长度的，所以代码一开始的复杂程度可想而知

对于本题其实就是一个前缀和加滑动窗口的思想，平时按照我这个思想去写的话完全没有问题，一开始我也是分不清滑动窗口和暴力，如下面的样例所示，一开始的解决我还是按照传统意义上的双循环遍历暴力解决,所以复杂度还是o(n*n)

class Solution {public long countSubarrays(int[] nums, long k) {int n = nums.length;// int number = (n+1)*n/2;int[] s = new int[n+1];// int[][] ans = new int[n + 1][n + 1];// 计算前缀和数组for (int i = 1; i <= n; i++) {s[i] = s[i - 1] + nums[i-1];}// int key=1;long total = 0;for(int l=1;l<=n;l++){int r = l;while(r<=n){int sum = s[r]-s[l-1];// ans[r-l+1][key] = sum;if(sum*(r-l+1) < k) total++;r++;}// key++;}// for(int i=1;i<=n;i++){//     for(int j=1;j<=n;j++){//         // System.out.println("ans[i][j]:"+ans[i][j]+",i:"+i+",j:"+j);//         if(ans[i][j]!=0&&(ans[i][j]*i)<k) total++;//     }// }return total;}
}

无论怎么优化依旧还超时过不了关，这是由于在我的遍历逻辑中还是去固定了左节点，然后一一遍历，这样会导致时间复杂度过高，也就当然会超时了。而滑动窗口的根本思想是外循环右扩展，内循环左收缩，并且r和l都不需要再一一初始化，保持更新即可。
其实最难的应该就是找到最简单的对应关系能联系到题目之中。

class Solution {public long countSubarrays(int[] nums, long k) {int n = nums.length;long total = 0;long sum = 0;int r = 0;for (int l = 0; l < n; l++) {while (r < n && (sum + nums[r]) * (r - l + 1) < k) {sum += nums[r];r++;}total += r - l;sum -= nums[l];}return total;}
}

我还是解释一下题解给的答案

题解的答案很简单就是将我上述的前缀和与滑动窗口结合到了一起，说是简单，但还是很难想到的，因为大多数人的思维都是单向的解决问题的思维，如我一般就是蹦着解决目的去的，并且过程也很符合题目的描述，扯远了，对于该题解，举个例子

示例[1,2,3,4,5] k=10
第一遍遍历 1*1<10 符合
第二遍遍历(1+2)*2<10符合
第三遍遍历(1+2+3)*3>=10不符合此时r=2并记录下total+=r-l=2 将sum的值更新为2
第四遍遍历(2+3)*2>=10不符合此时r=2 并再次记录下total+=r-l=3 将sum的值更新为2-2=0
第五遍遍历3*1<10 符合此时r=2,l=2
第六遍遍历(3+4)*2>=10 不符合此时r=3,l=2 并再次记录下total+=r-l=4 将sum的值更新为3-3=0；
依次往后继续遍历