题目重点：题目给 score=(连续区间和)×长度、要求 O(n)；本文明确非负数前提并用朴素双循环验证。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版统计连续且非空的子数组；所有元素为非负整数。题目有时写“子序列”，但公式和 index 移动更符合连续区间。
- 分数是区间元素和乘区间长度，等于 K 也计入；K<0 时非负分数无法满足。若允许负数，双指针单调性失效，不能声称本 O(n) 解仍正确。
解题路线
- 双指针维护当前 [left,right] 的元素和 sum；每向右加入一个非负值，score=sum×长度不会下降。
- 若 score>K，反复从左端移走值直到窗口合法或为空；非负性保证继续右移无法让原本超标的更长窗口变合法。
- 固定 right 且当前最左合法位置为 left，则所有以 right 结尾、起点在 [left,right] 的区间也合法，共 right−left+1 个。
- 对正数、零、K=0、空数组和所有单元素超标输入做手算；随机小数组与 O(n²) 枚举独立比较。
手动走一遍
values=[2,1,4,3,5]、K=5：每个单元素分数分别为 2、1、4、3、5，均合法；任何相邻双元素的 (sum×2) 都大于 5，因此结果 5，与题目相符。若 values=[0,0]、K=0，则 [0]、[0]、[0,0] 共 3 个。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Count contiguous nonnegative subarrays with sum * length <= threshold."""
def count_subarrays_with_score_at_most(values: list[int], threshold: int) -> int:
if any(value < 0 for value in values):
raise ValueError("linear sliding window requires nonnegative values")
if threshold < 0:
return 0
left = total = result = 0
for right, value in enumerate(values):
total += value
while left <= right and total * (right - left + 1) > threshold:
total -= values[left]
left += 1
result += right - left + 1
return result
复杂度
每个值最多进入和离开窗口一次，O(N) 时间、O(1) 额外空间；计数最多 N(N+1)/2，定长整数语言要考虑溢出。
易错点与追问
容易失分的边界
- 未确认连续区间就把任意子序列套滑窗。
- 输入允许负数时仍说扩大窗口分数单调。
- 只在当前窗口合法时加 1，漏掉所有以 right 结尾的更短合法区间。
- 把 score 写成 sum+length 或 sum/length。
继续深挖
- 有负数时，哪个单调论证首先失效？
- 如果只返回满足条件的最长长度而不是数量，怎样调整？
- 大量零值会让计数多大，返回类型如何选？
