滑动窗口这个专题里“恰好包含 K 个不同整数”的计数题一直很有迷惑性。我第一次在训练列表里看到第3859题时直接按照“窗口内不同数字个数等于 K 就计数”的思路去写结果示例过了一提交就挂在边界用例上。后来老老实实把问题拆开才意识到这类题的正解是先统计“最多包含 K 个不同整数”的子数组个数再统计“最多包含 K-1 个”两者之差就是答案。题目本身不复杂给定整数数组 nums 和整数 k统计连续子数组中有多少个恰好包含 k 种不同数值。适合正在刷双指针和哈希表计数的人也适合想在周赛前把“恰好”类问题一次吃透的同学。1. 题目理解与思路拆解1.1 题目到底在问什么题目说的“子数组”指的是原数组中连续的一段不是子序列。给定数组 nums 和整数 k我们要统计的是所有区间 [l, r] 的数量每个区间需要满足“区间内不同数值的种数恰好为 k”。举例来说nums [1,2,1,2,3]k 2答案就是 7。这 7 个子数组分别是[1,2]索引 0 到 1[1,2,1]索引 0 到 2[1,2,1,2]索引 0 到 3[2,1]索引 1 到 2[2,1,2]索引 1 到 3[1,2]索引 2 到 3[2,3]索引 3 到 4注意第三个和第六个虽然数值序列都是 [1,2]但它们来自数组的不同位置属于不同的子数组计数时都要算进去。这是计数题和集合题的重要区别子数组按位置区分不是按数值内容去重。另一个容易忽略的点是“不同整数”是按数值去重和出现次数无关。比如 [1,2,1,2] 虽然长度为 4但只包含 {1,2} 两种数值所以对 k2 是合法的。窗口里重复元素再多只要不引入新数值种类数就不变。这个特征从一开始就提醒我们统计时要用一个计数器去记录“当前窗口里出现过多少种数值”而不是简单的窗口长度。1.2 核心转换先算“最多 k”再减“最多 k-1”很多人一上来就想着怎么让窗口里的种类数“恰好等于 k”这个思路本身没有错但实现起来会有个大麻烦合法左端点的范围不好确定。更成熟的做法是绕一步定义一个辅助函数 f(t)表示“最多包含 t 个不同整数的子数组总个数”。任意一个子数组包含的不同整数种数一定是一个非负整数 j。f(k) 统计的是所有 j ≤ k 的子数组f(k-1) 统计的是所有 j ≤ k-1 的子数组。两者相减以后剩下的是什么正好是 j k 的那部分。因为 A_{k-1} 是 A_k 的子集子集减掉以后不会重复也不会有遗漏。用集合的话说就是A_k { 子数组 | 不同整数种数 ≤ k } A_{k-1} { 子数组 | 不同整数种数 ≤ k-1 }A_k \ A_{k-1} { 子数组 | 不同整数种数恰好等于 k }这个转换可以用一个生活类比来理解。想统计考试成绩恰好 90 分的学生可以先把 90 分及以下的人数统计出来再减去 89 分及以下的人数剩下的自然就是恰好 90 分的人。统计体重恰好 70kg 的人也一样用 70kg 及以下减去 69kg 及以下。不是只有“精确匹配”才能计数只要条件具有包含关系做差就是安全的。这个转换不是炫技它背后有一个很实际的考量“最多包含 k 个”是一个单调性质滑动窗口可以高效维护而“恰好包含 k 个”是一个等式条件直接维护会让合法左端点的范围变得支离破碎。稍后我会用反例说明为什么直接维护“恰好”很难。1.3 为什么“恰好”难维护而“最多”容易统计先看直接维护“恰好 K”会遇到什么问题。窗口扩大时种类数会依次经历 K-1、K、K1 这些状态。当你从 K-1 变到 K 时窗口内以当前右端点结尾的子数组并不是全都合法的因为如果把左边界往右移动一点种类数可能还是 K也可能变成 K-1。你无法通过一个简单公式在这个瞬间准确计数只能再去枚举左端点那就退化成 O(n^2) 了。再看右指针继续移动时的情况。窗口从 K 变成 K1你不得不收缩左指针但收缩到什么位置取决于重复元素的分布。比如某个重复元素已经被移出窗口种类数才真正减少这个“触发点”往往藏得很深每次调整都可能要移动很多步。更要命的是即使你把窗口缩回 K 了以当前右端点结尾的合法子数组数量也不是简单的窗口长度因为左边界往里缩一点可能仍然是恰好 K 种你需要再枚举一遍左端点复杂度直接爆炸。“最多 K”的性质就干净得多。只要窗口本身的种类数 ≤ K那么它的任意后缀子数组 [l, right] 都是窗口的子集种类数只可能更少不可能更多所以一定也满足“最多 K”。反过来任何不满足条件的左端点都已经被左指针越过因为它对应的区间种类数一定大于 K。这意味着以当前右端点结尾的合法左端点是一个连续区间 [left, right]数量就是 right - left 1。滑动窗口擅长维护这种“一旦合法往后延伸也合法”的单调边界。把“恰好”转换成“最多”本质上是把问题交给滑动窗口最擅长的形态。2. 滑动窗口统计“最多 K 个不同”的完整模板2.1 窗口右扩、左缩和累加的底层逻辑“最多 K 个不同”的统计函数 countAtMostK 是整套解法的心脏它的运行规则如下右指针 right 从 0 扫到 n-1每次把 nums[right] 加入哈希表 freq。如果 freq[nums[right]] 从 0 变成 1说明窗口里多了一种数值kinds 加 1。当 kinds k 时循环移出 nums[left]并让 left 向右移动。如果某个数值的频率减到了 0说明这种数值已经完全离开窗口kinds 减 1。一直收缩到 kinds ≤ k 为止。累加 right - left 1 到答案。第 4 步是最关键也最容易被问住的地方。为什么每次右指针移动一格只需要加一个窗口长度因为此时窗口 [left, right] 本身是合法的而任意左端点 l 落在 [left, right] 区间内时子数组 [l, right] 都是 [left, right] 的后缀。后缀包含的不同数值不会比整个窗口多所以这些子数组一定全部满足“最多 k 个不同”。同时任何左端点小于 left 的子数组在最坏情况下仍然包含被移出窗口的某些元素它的种类数一定大于 k所以不可能合法。合法左端点正好是连续的一段长度为 right - left 1数量直接算出来。这里还有一个容易误解的点left 并不是窗口的“任意左边界”而是“满足条件的最靠左的左边界”。它只向右移动不会回退这个单调性保证了整个算法是 O(n) 的。很多人把“最多 K”的窗口想成可以随意左右调整实际上右指针每次只走一步左指针只负责在条件被破坏时收紧边界边界一旦收紧就不会再放开因为后续元素只会让窗口越来越大种类数不会因为右移而减少。2.2 代码模板与实现注释C 版本如下。注意 countAtMostK 里对 k 0 的处理这个在 k 0 时会用到因为主函数要调用 countAtMostK(nums, k-1)当 k 0 时传进去的是 -1必须返回 0。class Solution { public: // 统计最多包含 k 个不同整数的子数组个数 long long countAtMostK(const vectorint nums, int k) { if (k 0) return 0; unordered_mapint, int freq; // 记录窗口中每种数值出现的次数 int n nums.size(); long long res 0; int left 0, kinds 0; for (int right 0; right n; right) { if (freq[nums[right]] 0) { kinds; // 第一次出现种类数增加 } while (kinds k) { // 收缩窗口直到种类数不超限 if (--freq[nums[left]] 0) { --kinds; // 某个数值彻底离开窗口种类数减少 } left; } res right - left 1; // 以 right 结尾的合法子数组个数 } return res; } long long subarraysWithKDistinct(const vectorint nums, int k) { if (k 0) return 0; return countAtMostK(nums, k) - countAtMostK(nums, k - 1); } };Python 版本更简洁适合快速验证思路def subarrays_with_k_distinct(nums, k): def at_most(k): if k 0: return 0 freq {} res 0 left 0 kinds 0 for right, x in enumerate(nums): freq[x] freq.get(x, 0) 1 if freq[x] 1: kinds 1 while kinds k: y nums[left] freq[y] - 1 if freq[y] 0: kinds - 1 left 1 res right - left 1 return res return at_most(k) - at_most(k - 1)如果题目保证元素值域很小比如数组元素都在 [0, n] 区间内可以把 unordered_map 换成定长数组例如vectorint freq(n 1, 0)省掉哈希表的常数开销。值域很大、元素可能为负数时哈希表更省心因为不需要额外处理下标偏移。2.3 用两个小例子验证累加公式光看公式容易觉得抽象我习惯用两个极端简单的例子把累加逻辑走一遍。第一个例子是 nums [1,1,1]k 1。countAtMostK(1) 的过程right 0 时窗口 [0,0] 合法累加 1right 1 时窗口 [0,1] 合法累加 2right 2 时窗口 [0,2] 合法累加 3总结果 6。而 [1,1,1] 的所有子数组确实是 3×4÷2 6 个全部只包含 1 种数值。可以看到每次加的是“以当前 right 结尾的合法子数组数量”不是窗口长度本身但在这个数组里两者刚好一致。第二个例子是 nums [1,2]k 1。countAtMostK(1)right 0 时窗口 [0,0]只有 [1] 合法累加 1right 1 时加入 2窗口 [0,1] 包含两种数值超出限制左指针收缩到 1窗口变成 [1,1]累加 1总结果 2。以 2 结尾且最多包含 1 种数值的子数组只有 [2] 一个公式 right - left 1 1 - 1 1 1正确。countAtMostK(0) 返回 0最终答案就是 2对应子数组 [1] 和 [2]。这两个例子直观展示了右扩、左缩、累加三者如何配合。3. 边界情况、复杂度与完整流程走查3.1 标准示例完整走查nums [1,2,1,2,3]k 2文字讲解不如表格直观。下面先走 countAtMostK(2) 的完整过程。窗口状态我用“收缩后的窗口”表示这个窗口是 map 的连续区间不是哈希表。right加入元素收缩后窗口kinds本次累加累计 res01[1]11112[1,2]22321[1,2,1]23632[1,2,1,2]241043[2,3]2212注意 right 4 时加入 3 后窗口 [0,4] 含有 1、2、3 三种数值超限。左指针连续移出 1、2、1直到窗口变成 [2,3]种类数回到 2。此时以 3 结尾且最多包含 2 种数值的子数组是 [2] 和 [2,3]正好 2 个所以累加 2。再走 countAtMostK(1) 的完整过程right加入元素收缩后窗口kinds本次累加累计 res01[1]11112[2]11221[1]11332[2]11443[3]115最后用 12 - 5 7和手工枚举的 7 个子数组完全对上。走查的价值在于它能让你直观看到为什么每次累加的是 right - left 1而不是别的数字。尤其是 right 4 那一步如果按“窗口长度”算会得 2按“结尾数量”枚举也是 2公式和枚举是一致的。3.2 容易踩的边界场景清单我把实际操作中需要注意的边界情况整理成一张表这样刷题的时候可以直接对照检查。场景行为与原因建议k 0非空子数组至少包含 1 种数值所以答案恒为 0主函数开头直接if (k 0) return 0;nums 为空数组没有子数组答案 0直接防御性返回 0数组全部相同且 k 1所有子数组都只有 1 种数值答案是 n×(n1)/2可用此公式快速验证算法正确性k 大于数组的不同数值总数不存在恰好包含 k 种的子数组f(k) 与 f(k-1) 相等差为 0不需要特判差值法天然处理元素包含负数、零或超大值哈希表按数值去重与具体数值大小无关直接用 unordered_map不要用 bool 数组n 很大子数组总数可能超过 int 范围结果可能超过 2^31 - 1累加用 long long特别强调一下 k 0 的情况。countAtMostK(0) 在模板里也能跑出正确结果因为它会不断收缩窗口直到空窗口每次累加 right - left 1 都是 0所以最终返回 0。但 left 会越过 right逻辑上看着别扭不如在主函数直接特判来得干净。3.3 复杂度分析与返回值类型选择时间复杂度是 O(n)空间复杂度取决于哈希表大小最坏 O(n)。这个 O(n) 是通过均摊分析得到的右指针一直往前走每个元素最多被加入窗口一次左指针虽然可能在某个 right 循环里连续移动多次但它总共最多向右移动 n 次因为 left 不会回退。你可以把窗口想成一条队伍每个元素最多被从队尾加进来一次、从队头移出去一次总操作次数是线性的。这比很多同学直觉里以为的“双重循环 O(n^2)”要快得多因为内层 while 移动的是同一个 left不是每一轮都从零开始。返回值类型建议直接用 long long。原因很简单n 100000 时子数组总数 n×(n1)/2 约等于 5×10^9已经超过 32 位 int 的上限 2147483647。虽然很多平台测试数据可能没这么大但为了稳妥累加器和最终答案都用 long long 没有任何坏处。我就在一个 n 50000 的全相同数组用例上翻过车答案算出来是个负数查了半天才发现是 int 溢出。4. 常见问题、排查技巧与同类扩展4.1 频率表更新顺序是最容易翻车的地方哈希表的更新顺序非常关键。错误版本长这样while (kinds k) { if (freq[nums[left]] 0) kinds--; // 错误此时还没减少频率几乎永远不成立 freq[nums[left]]--; left; }这个版本的问题在于先判断 freq[nums[left]] 是否为 0然后再执行--但判断发生在减少之前窗口里明明还留着这个元素频率几乎不可能为 0于是 kinds 该减的时候没有减最终结果偏大。正确写法一定是先执行频率自减再根据自减后的结果判断是否归零。这个过程可以类比食堂撤菜窗口里原本有三份宫保鸡丁你撤走一份还剩两份菜的种类没有变只有当最后一份也撤走了才算真正少了一个菜。还有一个常见错误是在移出元素后无条件执行kinds--认为只要左指针移动种类数就一定减少。事实是只有被移出元素是窗口里最后一次出现时种类数才会减少。所以if (--freq[nums[left]] 0) --kinds;里的 if 不能省。另外要留意收缩条件的方向。统计“最多 k”时收缩条件是while (kinds k)不是while (kinds k)。如果你写成大于等于本来合法的窗口也会被强行收缩left 会向右多走漏掉许多本应计数的子数组。这个 bug 的典型表现就是最终答案偏小而且很难从单个示例里看出来。4.2 调错时的三板斧与自查表调这类题我最推荐的策略是先单独验证 countAtMostK(k) 和 countAtMostK(k-1)不要直接盯着最终差值。差值不对必然是两个子函数中至少一个算错了先定位到具体是哪一个再进入下一步。第二步是打印每一轮的 left、kinds、freq 和 res对照手推表格。第三步是检查累加公式确认写的是res right - left 1而不是res 1也不是res right。下面是一张快速自查表可以按现象反推原因错误现象可能原因结果偏大收缩条件写成了kinds k或移出元素后没有正确更新 kinds结果偏小累加公式写错或移出时把非最后一次出现的元素也算成种类减少答案全是 0主函数误把 k 提前特判为 0或 countAtMostK 对 k 0 的处理提前返回了 0在取值很大的用例上报错数组越界检查是否把值域小的场景直接套了定长数组我还养成一个习惯用三个小样例快速回归。第一个是 [1,1,1]k1答案必须是 6第二个是 [1,2,1,2,3]k2答案必须是 7第三个是全相同数组但 k2答案必须是 0。这三个样例分别覆盖了“纯重复”“混合重复新元素”“无合法答案”三类情况跑通它们代码基本就稳了。4.3 从这道题延伸出去的几个变体如果把差值模板吃透它能解决的不只是这一道题。“至少包含 k 个不同整数的子数组数量”也能顺手算出来所有子数组总数是 n×(n1)/2减去最多包含 k-1 个不同整数的子数组数量剩下的就是至少 k 个。一个 f(t) 函数被反复复用这种“一个模板打天下”的感觉在刷题时非常高效。再看“最长子数组至多包含 k 个不同整数”这类题。它与本题的公分母完全一致都是滑动窗口维护“最多 k 个不同”只是累加的从“窗口右端点合法子数组个数”变成“更新最大窗口长度”。比如经典的“无重复字符的最长子串”也可以用类似框架只是那里的约束是单个字符最多出现一次判断条件略有不同。把 countAtMostK 里的res right-left1换成res max(res, right-left1)就能从计数题无缝切换到最值题。做字符串版本时哈希表可以是长度为 26 或 128 的定长数组因为字符种类有限。但要注意字符串题里的“不同字符”和“字符出现次数”是两套约束别搞混。“爱吃香蕉的狒狒”那种二分答案题虽然也带个 k但核心是“给定速度求能否在时间内吃完”属于单调函数求极值和滑动窗口统计窗口种类完全是两回事。判断一个题到底该用滑动窗口还是二分可以看问题的形式如果问“一共有多少个子数组满足某条件”优先想滑动窗口和前缀和如果问“求最小可行值且随参数单调”再考虑二分。一旦工具选对很多题都能套模板快速解决。最后分享一个我自己的调试习惯拿到这类题先把 countAtMostK 单独写好并验证再写主函数做差绝不要直接对着最终答案调 bug。还有返回值尽量用 long long我曾在 n50000 的全相同数组上吃过 int 溢出的亏答案变成负数排查了半天才找到原因。这道题和“爱吃香蕉的狒狒”那种二分模板很容易被放在一起混淆但只要判断清楚问题是“窗口内计数”还是“求极值单调”就不会选错工具。希望下次你在周赛或热题列表里再碰到“恰好 k 个不同整数”时直接套差值模板一次写对。