刷这道题的时候我卡了整整一个晚上原因特别朴素我一眼看出这是滑动窗口的套路但真动手写的时候发现窗口根本滑不起来。问题不在于维护窗口本身而在于题目问的是恰好包含k个不同整数——这种恰好的表述恰好卡死了滑动窗口最依赖的单调性条件。后来想明白用差分思想拆成两个最多问题才算是真正打开了局面。这篇就是把我的完整思路和踩坑过程整理出来给同样被这道题卡住的朋友一份可以直接抄作业的参考。先说清楚这道题到底在问什么给定一个整数数组nums和一个整数k要求返回其中恰好包含k个不同整数的子数组个数。子数组是连续的不同整数指同一个值只算一种。你要是第一次看到这题大概率会和我一样先想滑动窗口嘛窗口里维护一个计数表超过k就收缩左边界然后每移动一次右边界就累加答案。这个思路写出来跑一跑十有八九答案是错的或者根本不知道什么时候该统计答案。下面我会把原因拆开讲。1. 从直觉到卡壳为什么恰好k个不能直接套滑动窗口1.1 第一直觉窗口维护和收缩看起来都对我先写了个最朴素的版本。右边界right从0开始往右走维护一个哈希表记录窗口内每个数字出现的次数再维护一个变量distinct表示当前窗口里有几种不同数字。每次把nums[right]加进来之后如果distinct超过了k就收缩左边界把左边的数字移出去直到distinct又回到k。然后理所当然地认为现在窗口里的子数组都是恰好k个不同整数的了于是把窗口长度加到答案里。单看这个流程每一步都像是滑动窗口模板的正确姿势。如果题目问的是最多包含k个不同整数这个写法完全正确。可惜题目问的是恰好k个这就出现了问题当你收缩左边界到distinct等于k的那一刻窗口内部确实满足条件但窗口内不是所有子数组都满足条件。举例来说窗口内容如果是[a, b, a, c]distinct3子数组[a, b, a, c]本身确实有3个不同整数但它的子数组[b, a, c]也有3个[a, c]只有2个[a, b, a]只有2个。如果直接取窗口长度作为答案等于把不同起点产生的子数组全算了一遍那就乱套了。1.2 为什么滑动窗口模板在这里失效关键问题在于恰好这个条件不具备单调性。滑动窗口能正常工作依赖的是一个性质当右边界固定时随着左边界向右移动窗口内不同整数的数量是不增的。反过来当左边界固定时随着右边界向右移动不同整数的数量是不减的。因此对于最多k个这种条件窗口的可行性是单调的——一旦某段区间可行收缩它仍然可行而恰好k个这个条件在收缩窗口的过程中可能先满足、然后变得不满足、再然后又满足。比如上面那个例子[a, b, a, c]满足恰好3个收缩一位变成[b, a, c]还满足恰好3个再收缩一位变成[a, c]就只有2个了。同一个连续的收缩过程中恰好条件在true和false之间来回跳动。这就意味着你不能用一个简单的超了就收缩策略来确定左边界。如果卡到刚好等于k就停你只能保证当前整个窗口满足条件却没法回答以right结尾的子数组里到底有哪几个恰好有k种不同整数。理论上你可以枚举所有起点分别判断但那样就是O(n²)对于数据规模大的题必然超时。事实上这道题的经典解法是O(n)但思路不是硬维护恰好而是绕一道弯这也是这道题作为hard题的真正难点。1.3 换个角度看问题的收益卡了一晚上以后我冷静下来重新读题意识到恰好k个其实可以拆成最多k个减去最多k-1个。换句话说如果我能写一个函数f(t)返回数组里包含不同整数个数不超过t的子数组总数那么答案就是f(k) - f(k-1)。这是前缀和思想在计数问题里的经典应用。问题一下子被转化成了最多的滑动窗口——也就回到了我最熟悉的模板上。虽然多写了一个辅助函数但每个函数都是标准双指针总复杂度仍然是O(n)而且每个函数内的逻辑简单很多。这个转化就是整个题眼的解穴之处。2. 核心转化拆解为什么f(k) - f(k-1)恰好等于恰好k个2.1 集合的包含关系本质上是个前缀和先严格理一理这个转化为什么成立。设A_t是不同整数个数不超过t的子数组全体。显然A_{k-1}是A_k的子集因为不超过k-1个自然也不超过k个。记count(A)表示集合A中子数组的个数则count(A_k) - count(A_{k-1})就是不超过k个但也不属于不超过k-1个的那部分子数组的个数。用逻辑判断来说这些子数组满足distinct k同时又不满足distinct k-1那只能是distinct k。注意子数组的不同整数个数是整数不可能落在(k-1, k)之间所以差集恰好等于不同整数个数等于k的子数组集合。这个逻辑和值域无关和数组内容无关纯粹是集合运算所以它在所有测试用例下都成立。2.2 最多k个为什么就单调了现在的问题只剩f(t)能不能高效计算。有了最多这个前缀条件窗口的可行性就是单调的了固定右边界right当左边界left向右移动时窗口内不同整数个数t这件事一旦为真继续收缩左边界仍然为真因为移出元素不会增加不同整数的个数。同样固定left往右扩时条件可能从不满足变成满足但一旦满足左边界继续左移也没问题——当然我们的双指针算法里左边界只会右移所以只用前半段单调性就够了。因此我们维护一个左开右闭窗口[left, right)保证窗口内始终是满足distinct t的最大窗口。具体来说右边界每次扩展一格把nums[right]纳入计数。如果distinct超过了t说明当前窗口太宽就不断收缩左边界直到distinct回到t以内。此时以right为右端点的所有子数组凡是左端点落在[left, right]范围内的它们的distinct都t因为这段范围内的任意子数组都是当前合法窗口的子数组不同整数数不可能超过整个窗口。而左端点小于left的都对应一个曾经distinctt的更大的窗口不能要。于是以right结尾的合法子数组数量正好是right - left 1个。这个统计技巧很关键也是整个代码性能的核心。2.3 一个边界上的确认t等于0或数组长度时怎么办f(0)意味着最多0个不同整数也就是只允许空窗口但单独的每个子数组都至少包含1个元素、至少1种不同整数题目给nums[i]都是有效整数所以f(0)应该返回0。我在代码里用一个统一的逻辑处理了如果t 0直接返回0。因为当t0时任何非空窗口的distinct都至少为1右指针一扩展就会触发收缩最后right-left1永远为0。但为了对外层调用更安全显式判一下t 0会让行为更清晰。另一种边界是t 整个数组里的不同整数总数这时所有子数组都满足条件f(t)应该等于n * (n1) / 2滑动窗口逻辑也会自然给到这个结果不需要特判。3. 双指针版f(t)的完整实现与逐行解读3.1 先看核心代码C版本class Solution { private: long long atMostK(vectorint nums, int k) { int n nums.size(); unordered_mapint, int cnt; int left 0, distinct 0; long long ans 0; for (int right 0; right n; right) { if (cnt[nums[right]] 0) distinct; cnt[nums[right]]; while (distinct k) { cnt[nums[left]]--; if (cnt[nums[left]] 0) distinct--; left; } ans right - left 1; } return ans; } public: long long subarraysWithKDistinct(vectorint nums, int k) { return atMostK(nums, k) - atMostK(nums, k - 1); } };整个实现非常短核心就是atMostK这个函数。它的设计思路是始终维护一个合法的最大窗口每往窗口里塞一个右边的元素就以这个元素为右端点统计一次贡献。因为右端点固定左端点所有可能的位置中从left到right这r-left1个位置都可行于是累加这个数。循环结束后ans就是所有以任意元素为右端点、满足distinctk的子数组总数恰好覆盖了全部子数组不多不漏。3.2 为什么ans right - left 1是精确的这一步如果不理解后面写代码就很容易乱。假设当前窗口是[left, right]窗口本身满足distinctk。我在这一轮把right纳入窗口后窗口内任意子数组[left, right]只要left在[left, right]区间内它都是当前窗口的子数组所以它的distinct一定不超过当前窗口的distinct也就一定不超过k。反过来如果left left那么子数组[left, right]包含了一部分之前被我们排除掉的区间那个区间在收缩前distinct已经是k1了再加上右侧的这些元素distinct只能大于k不可能满足条件。所以可行左端点是连续的区间[left, right]数量正好是right-left1。这个思路就是经典固定右端点计数技巧在很多子数组统计题里都能复用。3.3 内存与性能哈希表该用unordered_map还是数组我最初写的是unordered_map版本简单直观。但LeetCode上这道题的数据范围是nums.length 10^5直接用unordered_map也能过只是常数略大。后来我改成数组版本因为nums[i]的范围通常是有界的比如1到10^5可以开一个vector cnt(n1, 0)直接按下标访问。但这有个前提是得先确认值域如果题目没说明值域还是unordered_map最稳妥。考虑到代码的通用性我会在答题时根据题目给定的数值范围选择——如果nums[i] nums.length直接数组计数更快否则就用哈希表。实际测试中数组版本大概能比unordered_map省10%到20%的时间在极大数据量下这个差距还是值得注意的。4. 从TLE到AC我实测过程中踩过的三个坑4.1 第一个版本为什么超时统计distinct时重复扫窗口我最开始写的atMostK非常朴素每扩展一次右边界就用一个临时哈希表重新数一遍[left, right]里有多少种不同整数然后再决定是否收缩。这个写法的正确性倒没问题但时间是O(n²)量级在最坏情况下重复扫窗口导致直接TLE。教训就是滑动窗口的distinct必须用增量方式维护。每加入一个元素nums[right]只有它自己可能引入新种类每移除一个元素nums[left]只有它自己可能让某个种类消失。所以用cnt数组做加减、维护一个distinct变量就能把每次窗口调整的成本降到O(1)整体才是O(n)。4.2 第二个版本答案偏小在错误的时机统计贡献这是我踩得最隐蔽的坑。我第二次把distinct改成了增量维护但代码结构是先收缩完窗口、再统一统计一次窗口长度然后错误地加了一个窗口内所有子数组数而不是以right结尾的子数组数。也就是说我在循环里写的是ans windowSize * (windowSize 1) / 2这会把窗口内每个子数组都重复计数。结果答案比正确值大很多一提交就WA。再往下调试改成ans right - left 1之后才对。我总结出来的规律是滑动窗口计数题里每次右指针移动一格后就累加当前窗口的某种值和收缩完毕后再累加整个窗口的统计量是两种完全不同思路必须按题目要求选对。本题的f(t)统计的是所有合法子数组总数应当按右端点固定累加而不是对整个窗口做组合计数。4.3 第三个坑int溢出答案必须用long long子数组总数最多是n*(n1)/2当n10^5时大约是5*10^9远超int的21亿上限。如果f(k)和f(k-1)都用int装中间哪怕不溢出最后两个数相减也可能得到错误结果。我把两个atMostK的返回值都改成long long以后这个问题就消失了。其实LeetCode题目返回值类型如果是int说明测试数据不会撑爆但我自己习惯一律用long long做中间计算避免边界数据卡我。注意函数内部的ans也必须用long long不能只在return时强转因为累加过程中就可能溢出。4.4 顺带一提哈希表的erase陷阱用unordered_map做计数器的时候如果某个数字的计数减到0我一开始没有把它从map里删掉而是靠cnt[nums[left]] 0来判断distinct应该减1。这个判断逻辑是对的只要别在遍历另一个维度时误以为这些0计数项仍然存在就好。更稳妥的做法是计数减到0时直接cnt.erase(nums[left])这样map.size()就能直接当作distinct。两种写法都可以但别混用。我实际测试中用erase会稍微增加常数开销所以更推荐保留计数为0的键用单独distinct变量维护。5. 同一套思路的扩展这道题的价值不止于一题5.1 扩展一恰好包含k个奇数/偶数的子数组个数把不同整数换成奇数以后本质上还是恰好多少个特征元素的问题。比如统计恰好包含k个奇数的子数组你一样可以直接用f(k)-f(k-1)其中f(t)表示最多包含t个奇数的子数组数。滑动窗口里的distinct变量换成oddCount就行。这说明恰好转最多再差分不是一道题的取巧而是一类计数问题的通用模板。遇到恰好正好不多不少这类字眼时优先想想能不能转换成两个最多做差。5.2 扩展二乘积小于k的子数组直接就是最多这道题是另一个常见变体统计乘积小于k的连续子数组个数。它的条件本身就是小于k天然满足单调性——子数组的乘积作为集合扩大时是增大的。所以直接用同样的双指针把distinct判断换成乘积比较即可。这里有个细节因为乘积可能很大不要真把子数组乘积存下来而是在移动右指针时维护当前窗口的成绩收缩左指针时通过除法恢复。这种窗口内聚合值随窗口缩扩而增减的模式和本题的distinct维护是一模一样的原理。5.3 通用判断法则什么时候可以直接滑什么时候要差分根据我做过的这类题总结出一条判断法则如果题目要求的子数组条件随窗口扩张呈现单调变化——例如乘积k元素和k不同元素数k——那么直接用一个双指针维护窗口即可如果条件不单调——例如恰好k正好大于等于m且小于等于n这类区间范围条件——就要先想清楚能否拆成两个单调条件的差。能用最多做差解决的问题几乎不会需要O(n log n)或更重的数据结构这也是面试和竞赛里最推崇的解法。判断方式就是问自己条件C是否满足若区间I满足C则I的任意子区间也满足C。如果答案为否那大概就需要拆条件或换思路。5.4 与另一种常用解法对比前缀和映射恰好k个不同整数还有一个思路是做映射把每个位置到它左边/右边最近重复数字的距离处理成某种前缀信息再用哈希表统计差值等于k的情况。这种方法在某些恰好k个问题上非常优雅比如统计奇偶性差分、统计和为k的子数组。但本题里不同整数这样一个非线性特征很难用单值前缀和表达硬套会很别扭。相比之下差分滑动窗口方案在实现和内存上都更优。我的建议是两种套路都掌握遇到具体题目时看条件选择——凡是能用最多做差解决的优先用这个因为代码模板最通用也最好调试。这一轮的实现经验里我最想强调的是一个看似hard的题拆成两个最多之后代码甚至比很多medium题还短。整体复杂度从脑中朴素的O(n²)降到O(n)代码只有二十行左右跑起来也很稳。如果你也正在被这类恰好k个的题折磨不妨先停下来把恰好翻译成最多再动手。很多时候算法提升不是靠写更多代码而是靠把条件改写得更可解。这个思路对同一类型的所有变体都管用值得花时间彻底吃透。