点击获取AI摘要

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

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

比方说，[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}$

问题分析

分数 monotonic 性质
对于正整数数组，子数组向右扩展会同时增加「和」与「长度」，因此分数

$\text{score}(l, r) = \left( \sum_{i=l}^{r} \text{nums}[i] \right) \times (r - l + 1)$

随着 $l$ 不变而 $r$ 增大时单调递增；同理，对于固定的右端点 $r$ ，若从左端点 $l$ 开始的子数组已满足 $\left( \sum_{i=l}^{r} \text{nums}[i] \right) \times (r - l + 1)<k$ ，那么从任意 $l' > l$ 开始到 $r$ 的子数组也必然满足该不等式，当 $l$ 增大（窗口缩小）时，分数单调递减。
利用双指针维护合法区间
- 用指针 l、r 表示当前窗口 $[l..r]$ 。
- 保证窗口内任何子数组（以任意左端点 $\ge l$ 出发、以 $r$ 结尾）的分数都严格小于 $k$ 。
- 随着 r 从左向右遍历，将 nums[r] 加入当前窗口的累加和 window_sum。
- 若此时 window_sum * (r-l+1) ≥ k，则不断收缩左端 l++（并从 window_sum 中减去 nums[l]），直到重新满足 < k。
计数方式
对于每个右端点 $r$ ，一旦窗口调到了最大合法大小 $[l..r]$ ，那么所有起点在 $l, l+1, \dots, r$ 的子数组都合法，共有 $r - l + 1$ 个。

算法思路

初始化：l = 0, window_sum = 0, ans = 0
遍历 r 从 0 到 n-1：
- window_sum += nums[r]
- 当 window_sum * (r - l + 1) ≥ k 时：
  1
  2
  3
  while l <= r and window_sum * (r - l + 1) >= k:
  window_sum -= nums[l]
  l += 1
- 此时 [l..r] 中所有子数组都合法，其数量为 r - l + 1，加到 ans。.
遍历结束，返回 ans。

时间复杂度

时间复杂度：指针 r 从左向右遍历一遍： $O(n)$ ；l 最多也只会从 $0$ 移动到 $n-1$ ： $O(n)$ ；合计 $O(n)$ 。

空间复杂度：只使用了若干常数变量， $O(1)$ 。

代码分解

初始化
  l = 0            # 窗口左端
  window_sum = 0   # 窗口 [l..r] 的元素和
  ans = 0          # 累计答案

遍历 r 从 0 到 n-1：
  1. 将 nums[r] 加入窗口和
     window_sum += nums[r]

  2. 如果窗口分数 >= k，则移动 l 收缩：
     while l ≤ r 且 window_sum * (r - l + 1) ≥ k:
         window_sum -= nums[l]
         l += 1
     # 结束后，[l..r] 窗口恢复到「所有子数组分数 < k」状态

  3. 以 r 为右端点的合法子数组有 (r - l + 1) 个，累加到 ans
     ans += (r - l + 1)

返回 ans

代码实现

from typing import List

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        """
        返回 nums 中所有分数 < k 的非空子数组数量。
        分数定义为 子数组之和 * 子数组长度。
        """
        n = len(nums)
        l = 0
        window_sum = 0
        ans = 0
        
        for r in range(n):
            window_sum += nums[r]
            # 收缩左端，直到窗口合法
            while l <= r and window_sum * (r - l + 1) >= k:
                window_sum -= nums[l]
                l += 1
            # 以 r 为右端点的所有子数组数
            ans += (r - l + 1)
        
        return ans

以 nums = [2,1,4,3,5], k = 10 为例：

步骤	r	加入 nums[r]	window_sum	l	检查 & 收缩	合法子数组数 r−l+1r-l+1r−l+1	累计 ans
初始	—	—	0	0	—	—	0
1	0	+2 → 2	2	0	$2*1<10$ ✓	0–0：1 个	1
2	1	+1 → 3	3	0	$3*2<10$ ✓	0–1：2 个	3
3	2	+4 → 7	7	0	$73=21\ge 10\times$ → 收缩 – remove 2 → sum=5, l=1 $52=10\ge 10\times$ → 收缩 – remove 1 → sum=4, l=2	2–2：1 个	4
4	3	+3 → 7	7	2	$72=14\ge 10\times$ → 收缩 – remove 4 → sum=3, l=3 $31=3 < 10\times$ ✓	3–3：1 个	5
5	4	+5 → 8	8	3	$82=16\ge 10\times$ → 收缩 – remove 3 → sum=5, l=4 $51=5 < 10$ ✓	4–4：1 个	6