2302. 统计得分小于 K 的子数组数目

题目链接：https://leetcode.cn/problems/count-subarrays-with-score-less-than-k/

代码

/**
 * 2302. 统计得分小于 K 的子数组数目
 * https://leetcode.cn/problems/count-subarrays-with-score-less-than-k/
 */

function countSubarrays(nums: number[], k: number): number {
    let left = 0;
    let res = 0;
    let sum = 0;
    for (let i = 0; i < nums.length; i++) {
        sum += nums[i];
        while (sum * (i - left + 1) >= k) {
            sum -= nums[left];
            left++;
        }
        if (sum * (i - left + 1) < k) {
            res += i - left + 1;
        }
    }
    return res;
}

思路

题目定义子数组的「得分」为：子数组元素和 sum 乘以子数组长度 len，要求统计所有得分 < k 的子数组数量。

• 核心观察：如果我们固定右端点 i，那么所有以 i 结尾的合法子数组的左端点一定是一个连续区间 [left, i]，可以用双指针维护。

• 滑动窗口：

  • 用 left 表示当前窗口左端点，sum 表示窗口内的和。
  • 枚举右端点 i，把 nums[i] 加入窗口后，不断移动 left，直到当前窗口得分 sum * (i - left + 1) < k。
  • 当窗口 [left, i] 合法时，以 i 为右端点、且得分小于 k 的子数组个数就是 i - left + 1，全部累加到答案中。

• 正确性：窗口在扩张时只会让得分更大，一旦不合法就收缩左端点，直到再次合法；由于 left 只向右移动，每个元素进出窗口至多一次。

• 复杂度：

  • 时间复杂度：(O(n))
  • 空间复杂度：(O(1))