统计满足规则的窗口
至多 K 个减去至多 K-1 个的技巧
统计满足规则的窗口 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
计数，而非度量
有时您必须统计满足规则的子数组数量，而不是寻找最长的子数组。一个小技巧就能将它转化为简单的滑动窗口问题。🔢
恰好 K 个的难题
直接统计恰好包含 K 个目标的子数组并不容易。边界会不断变化，因此很难维护一个简洁的窗口。
改为统计至多 K 个
使用一个窗口来统计至多 K 个目标的子数组要容易得多。向右扩展时，每个有效的左端点都会对应一个可计数的子数组。
减法技巧
恰好 K 个等于 atMost(K) 减去 atMost(K - 1)。将两个容易计算的数量组合起来，就能得到实际想要的复杂结果。
answer = at_most(k) - at_most(k - 1)构建辅助函数
请编写一个统计至多 k 个目标的子数组数量的函数。它维护一个滑动窗口，并在计数超过 k 时收缩窗口。
def at_most(k):
left = 0
total = 0违反条件时收缩
向右扩展并更新窗口。当窗口包含更多于 k 个目标时，将左指针向前移动，使窗口回到允许范围内。
while count > k:
# remove a[left]
left += 1加入窗口计数
修正窗口后，所有以右端点结尾、起点从左端点到右端点的子数组都有效。请加入右减左加一。
total += right - left + 1为什么这个计数成立
对于固定的右端点，有效起点可以是左端点、左端点+1，一直到右端点。这正好是 right - left + 1 个子数组，并且都满足至多 k 个的条件。
组合两次调用
运行两次辅助函数并进行减法。每次调用的复杂度都是 O(n)，因此完整的恰好 K 个计数整体仍然是线性的。
return at_most(k) - at_most(k - 1)处理边界情况
当 k 为零时，atMost(k - 1) 会使用负一。请处理这种情况，使辅助函数仍能返回合理的零计数。
适用场景
“至多减去至多”这一思路适用于统计恰好包含 K 个不同值、K 个奇数，或满足任何按窗口具有单调性的属性的子数组。
快速检查
您希望统计恰好包含 K 个不同元素的子数组数量。
回顾
统计恰好 K 个就是 atMost(K) 减去 atMost(K - 1)。每个辅助函数都在 O(n) 时间内滑动窗口，因此整个计数过程仍然是线性的。✅
用 AI 导师学习 Python — 免费
在浏览器中编写并运行真实代码，获得全天候 AI 导师的即时帮助，并在网页或应用中继续学习。
- 课程
- 30
- 课程
- 120
常见问题解答
「统计满足规则的窗口」课时是免费的吗？
是的 — 「统计满足规则的窗口」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「统计满足规则的窗口」这节课中我会学到什么？
至多 K 个减去至多 K-1 个的技巧 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「统计满足规则的窗口」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。