企业官网建设流程全解析

刷这道题的时候我卡了整整一个晚上，原因特别朴素：我一眼看出这是滑动窗口的套路，但真动手写的时候发现窗口根本滑不起来。问题不在于维护窗口本身，而在于题目问的是"恰好包含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]，distinct=3，子数组[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的，都对应一个曾经distinct>t的更大的窗口，不能要。于是以right结尾的合法子数组数量正好是right - left + 1个。这个统计技巧很关键，也是整个代码性能的核心。

2.3 一个边界上的确认：t等于0或数组长度时怎么办

f(0)意味着最多0个不同整数，也就是只允许空窗口，但单独的每个子数组都至少包含1个元素、至少1种不同整数（题目给nums[i]都是有效整数），所以f(0)应该返回0。我在代码里用一个统一的逻辑处理了：如果t <= 0，直接返回0。因为当t=0时，任何非空窗口的distinct都至少为1，右指针一扩展就会触发收缩，最后right-left+1永远为0。但为了对外层调用更安全，显式判一下t <= 0会让行为更清晰。另一种边界是t >= 整个数组里的不同整数总数，这时所有子数组都满足条件，f(t)应该等于n * (n+1) / 2，滑动窗口逻辑也会自然给到这个结果，不需要特判。

3. 双指针版f(t)的完整实现与逐行解读

3.1 先看核心代码（C++版本）

class Solution { private: long long atMostK(vector<int>& nums, int k) { int n = nums.size(); unordered_map<int, 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(vector<int>& nums, int k) { return atMostK(nums, k) - atMostK(nums, k - 1); } };

整个实现非常短，核心就是atMostK这个函数。它的设计思路是：始终维护一个合法的最大窗口，每往窗口里塞一个右边的元素，就以这个元素为右端点统计一次贡献。因为右端点固定，左端点所有可能的位置中，从left到right这r-left+1个位置都可行，于是累加这个数。循环结束后ans就是所有以任意元素为右端点、满足distinct<=k的子数组总数，恰好覆盖了全部子数组，不多不漏。

3.2 为什么"ans += right - left + 1"是精确的

这一步如果不理解，后面写代码就很容易乱。假设当前窗口是[left, right]，窗口本身满足distinct<=k。我在这一轮把right纳入窗口后，窗口内任意子数组[left', right]，只要left'在[left, right]区间内，它都是当前窗口的子数组，所以它的distinct一定不超过当前窗口的distinct，也就一定不超过k。反过来，如果left' < left，那么子数组[left', right]包含了一部分之前被我们排除掉的区间，那个区间在收缩前distinct已经是k+1了，再加上右侧的这些元素，distinct只能大于k，不可能满足条件。所以可行左端点是连续的区间[left, right]，数量正好是right-left+1。这个思路就是经典"固定右端点计数"技巧，在很多子数组统计题里都能复用。

3.3 内存与性能：哈希表该用unordered_map还是数组

我最初写的是unordered_map版本，简单直观。但LeetCode上这道题的数据范围是nums.length <= 10^5，直接用unordered_map也能过，只是常数略大。后来我改成数组版本：因为nums[i]的范围通常是有界的（比如1到10^5），可以开一个vector cnt(n+1, 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*(n+1)/2，当n=10^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个"的题折磨，不妨先停下来，把"恰好"翻译成"最多"再动手。很多时候算法提升不是靠写更多代码，而是靠把条件改写得更可解。这个思路对同一类型的所有变体都管用，值得花时间彻底吃透。