[LeetCode] 每日一题 2302. 统计得分小于 K 的子数组数目（经典滑窗）

题目描述

一个数组的 分数 定义为数组之和 乘以 数组的长度。

• 比方说，[1, 2, 3, 4, 5] 的分数为 (1 + 2 + 3 + 4 + 5) * 5 = 75 。

给你一个正整数数组 nums 和一个整数 k ，请你返回 nums 中分数 严格小于 k 的 非空整数子数组数目。

子数组 是数组中的一个连续元素序列。

题目链接

https://leetcode.cn/problems/count-subarrays-of-length-three-with-a-condition

示例输入

示例 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

解题思路

今天这题又是非常典型的滑动窗口问题 🚀。题目要求我们统计子数组中分数小于 k 的数量，分数定义为 子数组元素和 × 子数组长度。

仔细观察可以发现，随着滑动窗口右端点的扩展，子数组长度增加，总和增加，因此分数整体是单调上升的；而收缩左端点可以有效降低分数。
因此，我们可以采用单向滑动窗口来做，维护一个窗口 [left, right]，每次向右扩展 right，如果当前窗口的分数不满足小于 k，就不断移动左端点 left 来缩小窗口直到条件满足，然后累加当前窗口内的子数组数量。

整体逻辑非常顺畅，是最近几天滑窗应用的经典模式之一！

代码实现

class Solution {
    public long countSubarrays(int[] nums, long k) {
        long ans = 0;
        int left = 0;
        long sum = 0;
        int n = nums.length;
        for (int right = 0; right < n; right++) {
            sum += nums[right];
            while (sum * (right - left + 1) >= k) {
                sum -= nums[left];
                left++;
            }
            ans += (right - left) + 1;
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n)

  • 每个元素最多被加入和移除窗口一次，因此整体遍历是线性的。

• 空间复杂度：O(1)

  • 只使用了常数个额外变量，没有引入额外的数据结构。

总结

这道题再次验证了滑动窗口技巧在子数组问题中的威力 💪。关键在于正确理解窗口扩展和收缩的条件，从而保证窗口内始终满足要求。
思路清晰简单，代码实现流畅，是非常适合巩固滑窗思维的一题！

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。