去年系统刷滑动窗口专题的时候被 LintCode 3899 这道题卡了整整两天。题目全称是“K 个不同整数的子数组”方法签名是public int subarraysWithDistinct(int[] nums, int k)。如果你在别的刷题平台见过它那大概率是 LeetCode 992两边是同一道题。题面一句话就能说清给定一个整数数组nums和一个整数k返回数组里恰好由k个不同整数组成的连续子数组的个数。第一反应是暴力枚举所有子数组、用HashSet数不同整数的人估计不止我一个。但看一眼数据范围就清醒了nums.length最大能到2 * 10^4全部子数组数量是n*(n1)/2接近两亿个。每个子数组再单独做一次去重统计这复杂度在面试环境下基本等于自杀。题目真正想考的是滑动窗口加计数再加上一个非常关键的数学转化把“恰好 k 个不同整数”转成“最多 k 个不同整数”减“最多 k−1 个不同整数”。这个转化才是整道题的点睛之笔。这篇文章不打算只贴一份能过编译的代码。我会把这个转化为什么成立、滑动窗口为什么能数出子数组数量、手写代码时哪里最容易翻车以及这套计数思想还能复用在哪几道题上一次讲透。适合正在准备 Java 后端面试的朋友也适合滑动窗口刷了大几十道、但遇到“恰好”“等于”型题目还是发怵的人。1. 先看清楚题目它到底在问什么1.1 原题场景与官方样例走读题目给了一个数组nums和一个整数k要求统计所有满足条件的连续子数组子数组中出现过的不同整数个数恰好等于k。有几个细节容易被忽略子数组是连续的不是子序列重复出现的元素只算一个不同整数“恰好”意味着多一个不行、少一个也不行。看标准样例。nums [1,2,1,2,3]k 2手数一下符合条件的子数组是[1,2]、[2,1]、[1,2]、[2,3]、[1,2,1]、[2,1,2]、[1,2,1,2]一共 7 个。为什么[1,2,1,2,3]不算因为整个数组有 1、2、3 三个不同整数大于 2。为什么[1,2,3]不算同理。这个样例看着简单但它正好暴露了暴力枚举的痛点枚举每个子数组都要重新统计一遍“有哪些数”大量重复劳动。再看一个边界型例子nums [1,1,1,1]k 1。所有子数组都只包含一个不同整数答案是4321 10。如果k 2答案是 0因为整个数组的不同整数个数都不超过 1不可能有恰好 2 个不同整数的子数组。这类极简用例很适合本地自测后面我会单独列一份测试清单。题目还藏了一个不起眼的约束1 nums[i] nums.length。也就是说每个元素的值落在数组长度范围内。这个限制在第三章写数组计数版本时可以直接利用把HashMap换成int[]性能还能再提一截。1.2 “恰好 k 个”让滑动窗口变难在哪滑动窗口最擅长处理的是“最多不超过多少”这类约束。因为收缩时机非常直观窗口内不满足条件了就把左边界一直往右移直到重新满足。求“最长无重复子串”“至多 k 个不同字符的最长子串”都是这个套路。但“恰好等于 k 个不同整数”就很尴尬。窗口扩大时不同整数数量可能从 k−1 跳到 k再跳到 k1你没法让窗口稳定停在一个精确状态。左指针移动时也一样可能移一位还在 k再移一位就变 k−1 了。如果强行用单个滑动窗口维护“恰好 k 个”就得同步维护一摞边界信息代码很容易写成一团乱麻。更本质的思维陷阱在于很多人看到“恰好”会下意识地去枚举左端点、找右端点的合法区间。但这个问题里右端点既有下界又有上界要用两条边界夹出来代码复杂度直接上了一个台阶。所以标准解法干脆绕开这个难点不直接数“恰好 k 个”而是先数“最多 m 个”再用两个“最多”相减。1.3 核心转化恰好 最多 k − 最多 k−1定义一个函数f(m)数组nums中包含的不同整数数量不超过m的子数组总个数。那么“恰好 k 个不同整数”的子数组一定会被f(k)数进去但它不会被f(k−1)数进去因为f(k−1)要求不同整数数量不超过 k−1。反过来看任何一个被f(k)数到、却没被f(k−1)数到的子数组它满足两个条件——不同整数数量大于等于 k否则会被f(k−1)数到同时不超过 k因为被f(k)数到了。两边一夹正好是“恰好等于 k”。所以恰好 k 个不同整数的子数组数量 f(k) − f(k−1)这个转化是我认为本题最值钱的一步。我最早学滑动窗口的时候总觉得“做减法”有点投机取巧。后来刷的题多了才明白这其实是一种通用归约思想精确区间不好直接统计那就统计上界之内减去下一个上界之内剩下的自然就是精确区间。这套思想在后面的 LeetCode 1248 里你会再次遇到一模一样。时间上f(k)和f(k−1)各跑一次整体复杂度还是 O(n)只是常数乘了个 2完全可接受。2. 把答案拆成两个“最多”核心思路落地2.1 滑动窗口数子数组的经典套路现在问题被简化成怎么数出“最多包含 m 个不同整数”的子数组数量这一步就顺滑多了。维护一个滑动窗口窗口范围是[left, right]里面放的是当前所有可能成为合法子数组左端点的范围。我用一个哈希表记录窗口内每个元素出现的次数用哈希表的size()直接代表不同整数的个数。窗口的扩大和收缩规则一句话就能说清右指针right每走一步把nums[right]加进窗口计数加一如果不同整数数量超过m就收缩左指针把nums[left]移出窗口计数减一如果某个数字的计数减到了 0就从哈希表里删掉这个 key一直收缩到不同整数数量重新小于等于m为止。收缩完之后窗口是满足条件的。而且窗口里的所有左端点位置都可以和当前right组成合法子数组。这句话是整段代码的基石理解透了我下面说的计数公式才不晕。有一个容易踩的细节收缩左指针必须用while循环不能只用if移一次。因为移出一个元素后窗口内可能仍然超过 m 个不同整数必须一直移到满足条件为止。最极端的情况下如果窗口里全是同一个数那distinct永远为 1不管窗口多长都不会触发收缩。2.2 为什么每次累加 right - left 1这是滑动窗口计数模板里最需要想清楚的一行。当右指针固定在right时窗口收缩完毕后的左边界是left。此时任何从left到right之间的位置作为左端点和right组成的子数组都一定满足“不同整数数量不超过 m”。为什么因为这些子数组都是当前窗口的子集窗口内不同整数都不超过 m子集只会更少不会更多。那左端点在left之前的位置呢比如left−1作为左端点它会把之前被移出窗口的某个元素重新包进来。那个元素很可能就是导致不同整数数量重新超标的元凶所以不能算。于是以right结尾且满足条件的子数组数量恰好是right − left 1。这个推理的本质是把“固定右端点统计合法左端点个数”作为统计口径。注意这里不是求“最长满足条件的子数组长度”而是求数量所以不能只维护一个最大值必须每次右指针走完都累加一次。想通这一点后面看代码就会觉得每一行都顺理成章。2.3 手推一遍f(2) 是怎么算出来的光说公式容易飘。我用nums [1,2,1,2,3]、m 2手推一遍f(2)看看这个累加过程到底长什么样right加入元素收缩后窗口内容distinctleft本次增量res01[1]101112[1,2]202321[1,2,1]203632[1,2,1,2]2041043[2,3]23212重点看right 4这一步。加入3之后窗口[1,2,1,2,3]的 distinct 一下子变成 3超过 m2。于是左指针连续移动三次先移出下标 0 的 1窗口里还有下标 2 的 1distinct 仍是 3再移出下标 1 的 2窗口里还有下标 3 的 2distinct 仍是 3最后移出下标 2 的 1窗口变成[2,3]distinct 降到 2。此时left 3本次增量是4 − 3 1 2对应[2,3]和[3]这两个以4结尾的子数组。f(2)12验证无误。再看f(1)单元素子数组有 5 个长度大于 1 的没有全部相同的所以f(1)5。最终答案是12 − 5 7和官方样例完全一致。这个手推过程如果你能自己复现一遍这道题的核心思路基本就焊死在脑子里了。3. Java 实现从通用版到极致版3.1 HashMap 计数版通用且好理解先上最通用的版本适合nums[i]值域不可控、或者你懒得分析题目细节的情况。用HashMap存每个数字的出现次数用它的size()表示不同整数的数量代码语义最直观。class Solution { public int subarraysWithDistinct(int[] nums, int k) { return atMostK(nums, k) - atMostK(nums, k - 1); } private int atMostK(int[] nums, int m) { if (m 0) return 0; int left 0, res 0; MapInteger, Integer cnt new HashMap(); for (int right 0; right nums.length; right) { cnt.put(nums[right], cnt.getOrDefault(nums[right], 0) 1); while (cnt.size() m) { int val nums[left]; int c cnt.get(val); if (c 1) { cnt.remove(val); } else { cnt.put(val, c - 1); } left; } res right - left 1; } return res; } }两个实现细节值得展开。第一atMostK开头一定要if (m 0) return 0;。虽然题目保证k 1但主函数会调用atMostK(nums, k - 1)当k 1时传进去的就是 0。如果不特判cnt.size() 0这个循环条件会逼着左指针一路跑到left right最后res算出完全错误的结果。这个边界我至少见三个同学在面试现场踩过。第二移出左边界元素时先取当前计数c等于 1 就直接remove大于 1 就put成c−1。最忌讳的是只做cnt.put(val, cnt.get(val) - 1)却忘了删掉减到 0 的 key那样cnt.size()里残留“幽灵 key”窗口判断必挂。3.2 数组计数版把值域优势用起来题目里给了隐藏条件1 nums[i] nums.length这意味着所有元素值都落在一个已知区间。直接开一个长度为n1的int[]当计数器省去哈希计算和装箱开销实测性能提升非常明显。class Solution { public int subarraysWithDistinct(int[] nums, int k) { return atMostK(nums, k) - atMostK(nums, k - 1); } private int atMostK(int[] nums, int m) { if (m 0) return 0; int n nums.length; int[] cnt new int[n 1]; int left 0, distinct 0, res 0; for (int right 0; right n; right) { if (cnt[nums[right]] 0) distinct; cnt[nums[right]]; while (distinct m) { cnt[nums[left]]--; if (cnt[nums[left]] 0) distinct--; left; } res right - left 1; } return res; } }注意两个细节。第一cnt的下标直接用nums[right]本身因为数值范围是 1 到 n数组长度开n1就够下标 0 被浪费掉也无所谓。第二数组计数器没有自带的size()方法所以要手动维护distinct变量。加入元素时如果原计数是 0说明来了一个新数字distinct移出元素时如果减到了 0说明这个数字在窗口里绝迹了distinct--。我在本地用随机数组压测过数据规模两万时数组版比HashMap版快了 2 到 3 倍。不过如果你在面试中拿到的题目没有明确给值域别贸然用数组版宁可多写几行HashMap保证不出错。代码是给人跑的更是给面试官看的稳定优先。3.3 单遍扫描的双指针版面试加分项先做f(k)再减f(k−1)会扫描数组两遍。虽然复杂度还是 O(n)但有些追求极限的面试官会追问能不能一遍扫完可以。核心思路是同时维护两个左边界left1是满足“最多 k 个不同整数”的最左边界left2是满足“最多 k−1 个不同整数”的最左边界。右指针right每移动一次两个左指针分别按各自的约束收缩。此时以right结尾、恰好有 k 个不同整数的子数组左端点范围是[left1, left2)数量就是left2 − left1。这个版本对边界理解的要求高不少新手不建议优先写但当面试官的追问款很有意思。class Solution { public int subarraysWithDistinct(int[] nums, int k) { int n nums.length; int[] cnt1 new int[n 1]; int[] cnt2 new int[n 1]; int left1 0, left2 0; int distinct1 0, distinct2 0; int res 0; for (int right 0; right n; right) { if (cnt1[nums[right]] 0) distinct1; cnt1[nums[right]]; while (distinct1 k) { cnt1[nums[left1]]--; if (cnt1[nums[left1]] 0) distinct1--; left1; } if (cnt2[nums[right]] 0) distinct2; cnt2[nums[right]]; while (distinct2 k - 1) { cnt2[nums[left2]]--; if (cnt2[nums[left2]] 0) distinct2--; left2; } res left2 - left1; } return res; } }这里最容易写错的一行是res left2 - left1千万别写成left1 - left2。你可以在草稿纸上画一下left1收缩到“最多 k”它把“恰好 k”的左边界下限卡住了left2收缩到“最多 k−1”把“恰好 k”的左边界上限卡住了。左侧往右挪就是left1右侧再往右挪就是left2两个边界之间的长度才是合法左端点的个数。这个版本把两个HashMap换成两个数组计数器语义还挺清晰的。4. 刷题和面试中的高频坑位4.1 六个最容易翻车的细节这道题代码量不大但坑密密麻麻。我给自己列过一张清单每一条都是真实踩过的atMostK忘记处理m 0。这是第一大坑。前面说过k1时会调用atMostK(nums, 0)不特判直接崩。移出元素后不清理计数归零的 key。HashMap版特别常见后果是cnt.size()虚高窗口判断全错。数组版本的下标偏移搞错。因为数值从 1 开始cnt开n1是安全的。如果画蛇添足写nums[right] - 1反而可能越界或错位。res right - left忘了加 1。合法左端点数量是闭区间[left, right]的长度必须是right - left 1。少一个就是漏统计样例数据小的时候可能测不出来但大数组对拍一定翻车。收缩左边界用了if而不是while。这个特别隐蔽因为对小数组、小 k 来说有时候移一次刚好就满足了测试能过但数据一变就错。收缩必须循环到窗口重新合法为止。主函数里把两个参数写反。atMostK(nums, k)和atMostK(nums, k−1)的顺序反了会得到负数一看结果就知道但面试时很容易一紧张写反。4.2 边界输入与本地自测清单刷算法题最忌讳只跑题目样例。我自己总结了一份针对这题的本地自测清单nums [1]k 1结果应为 1nums [1]k 2结果应为 0nums [1,1,1,1]k 1结果应为 10nums [1,1,1,1]k 2结果应为 0nums [1,2,3,4,5]k 1只有 5 个单元素子数组满足结果应为 5nums [1,2,3,4,5]k 5整个数组就是唯一一个结果应为 1nums [1,2,1,2,3]k 2官方样例7。这些用例覆盖了最短数组、全相同数组、全不同数组和官方样例能一次性筛掉大部分边界 bug。我的习惯是写一个简单的测试main方法把这些用例全跑一遍再随机生成大数组和暴力解对拍。对拍是提升信心的利器本地暴力解怎么写都行只要答案正确。4.3 面试官追问与应对思路面试官八成会问“你这个解法时间复杂度多少”答O(n)。每个元素进窗口、出窗口最多各一次两遍扫描常数也就是 2。空间上HashMap版是 O(n)数组计数版是 O(max(nums[i]))而题目约束下它等价于 O(n)。如果面试官问“为什么不直接用单个滑动窗口维护恰好 k 个”不要只说“写起来复杂”可以从两个角度答一是单窗口难处理左边界收缩后的精确状态二是“恰好”类问题用上下界归约更系统f(k)−f(k−1)是通用套路。如果面试官继续深挖“能不能一遍扫完”把 3.3 的双指针版亮出来这属于超出预期的加分表现。还有个细节面试时先讲思路再写代码写的时候把m 0特判放在最前面顺手提一句“k1 时候这里会被传 0”面试官会认为你真懂边界而不是背模板。5. 举一反三这套模板还能解哪些题5.1 同思路的 LeetCode 题目清单“恰好等于 X 类”的计数问题几乎都能套f(k) − f(k−1)。和本题最接近的是 LeetCode 1248统计“优美子数组”数组里恰好有 k 个奇数的子数组。把奇数映射成 1、偶数映射成 0原题就变成了“恰好 k 个 1 的子数组”和 3899 几乎同一个解法非常适合放在同一天练。还有几道滑动窗口题虽然不是“恰好”型但用的是同一个窗口维护模板LeetCode 3无重复字符的最长子串单窗口加HashSetLeetCode 340至多 K 个不同字符的最长子串直接是“最多”型LeetCode 904水果成篮等价于至多 2 个不同字符的最长子数组LeetCode 76最小覆盖子串窗口内维护欠账计数逻辑稍复杂但骨架相似。把这五道题连起来刷一遍滑动窗口的“求最长、求最短、求数量”三种形态就齐了。5.2 一个能套用的滑动窗口模板我后来把这类计数滑窗模板固定成了五步定义窗口状态通常是计数器加一个“当前有多少种合法元素”的变量右指针每轮右移一位更新状态用while收缩左指针直到窗口重新满足约束每轮收缩完把“以右指针结尾的合法子数组数量”累加到答案如果题目要求“恰好”就构造f(x)函数做一次减法。这套模板对“最多”“至少”“恰好”三类约束都有用。区别只在于收缩条件和最后的统计方式。“最多”直接累加“至少”通常要配合欠账模型“恰好”就用减法归约。记熟练了面试遇到新题能快速定位到对应的变体。6. 个人刷题体会与后续扩展我个人的感受是LintCode 3899 的代码连三十行都不到难点全在思维转化。第一次做不出来太正常了我一开始也被“恰好”卡得很难受后来把“恰好等于最多减最多”这个套路背进脑子里同类题直接通了好几个。如果你正在准备面试建议把这题和 LeetCode 1248 放在同一天刷趁热打铁的效果比我这样隔了一周再遇到、重新推导一遍要强太多。还有个很笨但很有效的经验刷完 AC 只是第一步第二天把代码删掉重新写一遍能默写出来才算真会。我练滑动窗口专题时每道核心题都重复了三遍以上第一遍照着题解抄第二遍合上题解自己推边界第三遍模拟面试边讲边写。3899 就是靠这个方法从“会做”变成“肌肉记忆”的。如果你也把这道题吃透了接下来的扩展方向很明确。一个是看看 LeetCode 395“至少有 K 个重复字符的最长子串”那道题需要枚举字符种类数思路更宏观但底层还是这套窗口维护。另一个是去理解“上下界归约”思想在其他计数题里的应用比如前缀和计数、差分数组本质都是先把精确条件放宽成上界或下界再通过加减把精确区间夹出来。算法这东西模型见多了新题就都是老朋友换马甲。
滑动窗口进阶：如何用“恰好K个不同整数”破解子数组计数问题
去年系统刷滑动窗口专题的时候被 LintCode 3899 这道题卡了整整两天。题目全称是“K 个不同整数的子数组”方法签名是public int subarraysWithDistinct(int[] nums, int k)。如果你在别的刷题平台见过它那大概率是 LeetCode 992两边是同一道题。题面一句话就能说清给定一个整数数组nums和一个整数k返回数组里恰好由k个不同整数组成的连续子数组的个数。第一反应是暴力枚举所有子数组、用HashSet数不同整数的人估计不止我一个。但看一眼数据范围就清醒了nums.length最大能到2 * 10^4全部子数组数量是n*(n1)/2接近两亿个。每个子数组再单独做一次去重统计这复杂度在面试环境下基本等于自杀。题目真正想考的是滑动窗口加计数再加上一个非常关键的数学转化把“恰好 k 个不同整数”转成“最多 k 个不同整数”减“最多 k−1 个不同整数”。这个转化才是整道题的点睛之笔。这篇文章不打算只贴一份能过编译的代码。我会把这个转化为什么成立、滑动窗口为什么能数出子数组数量、手写代码时哪里最容易翻车以及这套计数思想还能复用在哪几道题上一次讲透。适合正在准备 Java 后端面试的朋友也适合滑动窗口刷了大几十道、但遇到“恰好”“等于”型题目还是发怵的人。1. 先看清楚题目它到底在问什么1.1 原题场景与官方样例走读题目给了一个数组nums和一个整数k要求统计所有满足条件的连续子数组子数组中出现过的不同整数个数恰好等于k。有几个细节容易被忽略子数组是连续的不是子序列重复出现的元素只算一个不同整数“恰好”意味着多一个不行、少一个也不行。看标准样例。nums [1,2,1,2,3]k 2手数一下符合条件的子数组是[1,2]、[2,1]、[1,2]、[2,3]、[1,2,1]、[2,1,2]、[1,2,1,2]一共 7 个。为什么[1,2,1,2,3]不算因为整个数组有 1、2、3 三个不同整数大于 2。为什么[1,2,3]不算同理。这个样例看着简单但它正好暴露了暴力枚举的痛点枚举每个子数组都要重新统计一遍“有哪些数”大量重复劳动。再看一个边界型例子nums [1,1,1,1]k 1。所有子数组都只包含一个不同整数答案是4321 10。如果k 2答案是 0因为整个数组的不同整数个数都不超过 1不可能有恰好 2 个不同整数的子数组。这类极简用例很适合本地自测后面我会单独列一份测试清单。题目还藏了一个不起眼的约束1 nums[i] nums.length。也就是说每个元素的值落在数组长度范围内。这个限制在第三章写数组计数版本时可以直接利用把HashMap换成int[]性能还能再提一截。1.2 “恰好 k 个”让滑动窗口变难在哪滑动窗口最擅长处理的是“最多不超过多少”这类约束。因为收缩时机非常直观窗口内不满足条件了就把左边界一直往右移直到重新满足。求“最长无重复子串”“至多 k 个不同字符的最长子串”都是这个套路。但“恰好等于 k 个不同整数”就很尴尬。窗口扩大时不同整数数量可能从 k−1 跳到 k再跳到 k1你没法让窗口稳定停在一个精确状态。左指针移动时也一样可能移一位还在 k再移一位就变 k−1 了。如果强行用单个滑动窗口维护“恰好 k 个”就得同步维护一摞边界信息代码很容易写成一团乱麻。更本质的思维陷阱在于很多人看到“恰好”会下意识地去枚举左端点、找右端点的合法区间。但这个问题里右端点既有下界又有上界要用两条边界夹出来代码复杂度直接上了一个台阶。所以标准解法干脆绕开这个难点不直接数“恰好 k 个”而是先数“最多 m 个”再用两个“最多”相减。1.3 核心转化恰好 最多 k − 最多 k−1定义一个函数f(m)数组nums中包含的不同整数数量不超过m的子数组总个数。那么“恰好 k 个不同整数”的子数组一定会被f(k)数进去但它不会被f(k−1)数进去因为f(k−1)要求不同整数数量不超过 k−1。反过来看任何一个被f(k)数到、却没被f(k−1)数到的子数组它满足两个条件——不同整数数量大于等于 k否则会被f(k−1)数到同时不超过 k因为被f(k)数到了。两边一夹正好是“恰好等于 k”。所以恰好 k 个不同整数的子数组数量 f(k) − f(k−1)这个转化是我认为本题最值钱的一步。我最早学滑动窗口的时候总觉得“做减法”有点投机取巧。后来刷的题多了才明白这其实是一种通用归约思想精确区间不好直接统计那就统计上界之内减去下一个上界之内剩下的自然就是精确区间。这套思想在后面的 LeetCode 1248 里你会再次遇到一模一样。时间上f(k)和f(k−1)各跑一次整体复杂度还是 O(n)只是常数乘了个 2完全可接受。2. 把答案拆成两个“最多”核心思路落地2.1 滑动窗口数子数组的经典套路现在问题被简化成怎么数出“最多包含 m 个不同整数”的子数组数量这一步就顺滑多了。维护一个滑动窗口窗口范围是[left, right]里面放的是当前所有可能成为合法子数组左端点的范围。我用一个哈希表记录窗口内每个元素出现的次数用哈希表的size()直接代表不同整数的个数。窗口的扩大和收缩规则一句话就能说清右指针right每走一步把nums[right]加进窗口计数加一如果不同整数数量超过m就收缩左指针把nums[left]移出窗口计数减一如果某个数字的计数减到了 0就从哈希表里删掉这个 key一直收缩到不同整数数量重新小于等于m为止。收缩完之后窗口是满足条件的。而且窗口里的所有左端点位置都可以和当前right组成合法子数组。这句话是整段代码的基石理解透了我下面说的计数公式才不晕。有一个容易踩的细节收缩左指针必须用while循环不能只用if移一次。因为移出一个元素后窗口内可能仍然超过 m 个不同整数必须一直移到满足条件为止。最极端的情况下如果窗口里全是同一个数那distinct永远为 1不管窗口多长都不会触发收缩。2.2 为什么每次累加 right - left 1这是滑动窗口计数模板里最需要想清楚的一行。当右指针固定在right时窗口收缩完毕后的左边界是left。此时任何从left到right之间的位置作为左端点和right组成的子数组都一定满足“不同整数数量不超过 m”。为什么因为这些子数组都是当前窗口的子集窗口内不同整数都不超过 m子集只会更少不会更多。那左端点在left之前的位置呢比如left−1作为左端点它会把之前被移出窗口的某个元素重新包进来。那个元素很可能就是导致不同整数数量重新超标的元凶所以不能算。于是以right结尾且满足条件的子数组数量恰好是right − left 1。这个推理的本质是把“固定右端点统计合法左端点个数”作为统计口径。注意这里不是求“最长满足条件的子数组长度”而是求数量所以不能只维护一个最大值必须每次右指针走完都累加一次。想通这一点后面看代码就会觉得每一行都顺理成章。2.3 手推一遍f(2) 是怎么算出来的光说公式容易飘。我用nums [1,2,1,2,3]、m 2手推一遍f(2)看看这个累加过程到底长什么样right加入元素收缩后窗口内容distinctleft本次增量res01[1]101112[1,2]202321[1,2,1]203632[1,2,1,2]2041043[2,3]23212重点看right 4这一步。加入3之后窗口[1,2,1,2,3]的 distinct 一下子变成 3超过 m2。于是左指针连续移动三次先移出下标 0 的 1窗口里还有下标 2 的 1distinct 仍是 3再移出下标 1 的 2窗口里还有下标 3 的 2distinct 仍是 3最后移出下标 2 的 1窗口变成[2,3]distinct 降到 2。此时left 3本次增量是4 − 3 1 2对应[2,3]和[3]这两个以4结尾的子数组。f(2)12验证无误。再看f(1)单元素子数组有 5 个长度大于 1 的没有全部相同的所以f(1)5。最终答案是12 − 5 7和官方样例完全一致。这个手推过程如果你能自己复现一遍这道题的核心思路基本就焊死在脑子里了。3. Java 实现从通用版到极致版3.1 HashMap 计数版通用且好理解先上最通用的版本适合nums[i]值域不可控、或者你懒得分析题目细节的情况。用HashMap存每个数字的出现次数用它的size()表示不同整数的数量代码语义最直观。class Solution { public int subarraysWithDistinct(int[] nums, int k) { return atMostK(nums, k) - atMostK(nums, k - 1); } private int atMostK(int[] nums, int m) { if (m 0) return 0; int left 0, res 0; MapInteger, Integer cnt new HashMap(); for (int right 0; right nums.length; right) { cnt.put(nums[right], cnt.getOrDefault(nums[right], 0) 1); while (cnt.size() m) { int val nums[left]; int c cnt.get(val); if (c 1) { cnt.remove(val); } else { cnt.put(val, c - 1); } left; } res right - left 1; } return res; } }两个实现细节值得展开。第一atMostK开头一定要if (m 0) return 0;。虽然题目保证k 1但主函数会调用atMostK(nums, k - 1)当k 1时传进去的就是 0。如果不特判cnt.size() 0这个循环条件会逼着左指针一路跑到left right最后res算出完全错误的结果。这个边界我至少见三个同学在面试现场踩过。第二移出左边界元素时先取当前计数c等于 1 就直接remove大于 1 就put成c−1。最忌讳的是只做cnt.put(val, cnt.get(val) - 1)却忘了删掉减到 0 的 key那样cnt.size()里残留“幽灵 key”窗口判断必挂。3.2 数组计数版把值域优势用起来题目里给了隐藏条件1 nums[i] nums.length这意味着所有元素值都落在一个已知区间。直接开一个长度为n1的int[]当计数器省去哈希计算和装箱开销实测性能提升非常明显。class Solution { public int subarraysWithDistinct(int[] nums, int k) { return atMostK(nums, k) - atMostK(nums, k - 1); } private int atMostK(int[] nums, int m) { if (m 0) return 0; int n nums.length; int[] cnt new int[n 1]; int left 0, distinct 0, res 0; for (int right 0; right n; right) { if (cnt[nums[right]] 0) distinct; cnt[nums[right]]; while (distinct m) { cnt[nums[left]]--; if (cnt[nums[left]] 0) distinct--; left; } res right - left 1; } return res; } }注意两个细节。第一cnt的下标直接用nums[right]本身因为数值范围是 1 到 n数组长度开n1就够下标 0 被浪费掉也无所谓。第二数组计数器没有自带的size()方法所以要手动维护distinct变量。加入元素时如果原计数是 0说明来了一个新数字distinct移出元素时如果减到了 0说明这个数字在窗口里绝迹了distinct--。我在本地用随机数组压测过数据规模两万时数组版比HashMap版快了 2 到 3 倍。不过如果你在面试中拿到的题目没有明确给值域别贸然用数组版宁可多写几行HashMap保证不出错。代码是给人跑的更是给面试官看的稳定优先。3.3 单遍扫描的双指针版面试加分项先做f(k)再减f(k−1)会扫描数组两遍。虽然复杂度还是 O(n)但有些追求极限的面试官会追问能不能一遍扫完可以。核心思路是同时维护两个左边界left1是满足“最多 k 个不同整数”的最左边界left2是满足“最多 k−1 个不同整数”的最左边界。右指针right每移动一次两个左指针分别按各自的约束收缩。此时以right结尾、恰好有 k 个不同整数的子数组左端点范围是[left1, left2)数量就是left2 − left1。这个版本对边界理解的要求高不少新手不建议优先写但当面试官的追问款很有意思。class Solution { public int subarraysWithDistinct(int[] nums, int k) { int n nums.length; int[] cnt1 new int[n 1]; int[] cnt2 new int[n 1]; int left1 0, left2 0; int distinct1 0, distinct2 0; int res 0; for (int right 0; right n; right) { if (cnt1[nums[right]] 0) distinct1; cnt1[nums[right]]; while (distinct1 k) { cnt1[nums[left1]]--; if (cnt1[nums[left1]] 0) distinct1--; left1; } if (cnt2[nums[right]] 0) distinct2; cnt2[nums[right]]; while (distinct2 k - 1) { cnt2[nums[left2]]--; if (cnt2[nums[left2]] 0) distinct2--; left2; } res left2 - left1; } return res; } }这里最容易写错的一行是res left2 - left1千万别写成left1 - left2。你可以在草稿纸上画一下left1收缩到“最多 k”它把“恰好 k”的左边界下限卡住了left2收缩到“最多 k−1”把“恰好 k”的左边界上限卡住了。左侧往右挪就是left1右侧再往右挪就是left2两个边界之间的长度才是合法左端点的个数。这个版本把两个HashMap换成两个数组计数器语义还挺清晰的。4. 刷题和面试中的高频坑位4.1 六个最容易翻车的细节这道题代码量不大但坑密密麻麻。我给自己列过一张清单每一条都是真实踩过的atMostK忘记处理m 0。这是第一大坑。前面说过k1时会调用atMostK(nums, 0)不特判直接崩。移出元素后不清理计数归零的 key。HashMap版特别常见后果是cnt.size()虚高窗口判断全错。数组版本的下标偏移搞错。因为数值从 1 开始cnt开n1是安全的。如果画蛇添足写nums[right] - 1反而可能越界或错位。res right - left忘了加 1。合法左端点数量是闭区间[left, right]的长度必须是right - left 1。少一个就是漏统计样例数据小的时候可能测不出来但大数组对拍一定翻车。收缩左边界用了if而不是while。这个特别隐蔽因为对小数组、小 k 来说有时候移一次刚好就满足了测试能过但数据一变就错。收缩必须循环到窗口重新合法为止。主函数里把两个参数写反。atMostK(nums, k)和atMostK(nums, k−1)的顺序反了会得到负数一看结果就知道但面试时很容易一紧张写反。4.2 边界输入与本地自测清单刷算法题最忌讳只跑题目样例。我自己总结了一份针对这题的本地自测清单nums [1]k 1结果应为 1nums [1]k 2结果应为 0nums [1,1,1,1]k 1结果应为 10nums [1,1,1,1]k 2结果应为 0nums [1,2,3,4,5]k 1只有 5 个单元素子数组满足结果应为 5nums [1,2,3,4,5]k 5整个数组就是唯一一个结果应为 1nums [1,2,1,2,3]k 2官方样例7。这些用例覆盖了最短数组、全相同数组、全不同数组和官方样例能一次性筛掉大部分边界 bug。我的习惯是写一个简单的测试main方法把这些用例全跑一遍再随机生成大数组和暴力解对拍。对拍是提升信心的利器本地暴力解怎么写都行只要答案正确。4.3 面试官追问与应对思路面试官八成会问“你这个解法时间复杂度多少”答O(n)。每个元素进窗口、出窗口最多各一次两遍扫描常数也就是 2。空间上HashMap版是 O(n)数组计数版是 O(max(nums[i]))而题目约束下它等价于 O(n)。如果面试官问“为什么不直接用单个滑动窗口维护恰好 k 个”不要只说“写起来复杂”可以从两个角度答一是单窗口难处理左边界收缩后的精确状态二是“恰好”类问题用上下界归约更系统f(k)−f(k−1)是通用套路。如果面试官继续深挖“能不能一遍扫完”把 3.3 的双指针版亮出来这属于超出预期的加分表现。还有个细节面试时先讲思路再写代码写的时候把m 0特判放在最前面顺手提一句“k1 时候这里会被传 0”面试官会认为你真懂边界而不是背模板。5. 举一反三这套模板还能解哪些题5.1 同思路的 LeetCode 题目清单“恰好等于 X 类”的计数问题几乎都能套f(k) − f(k−1)。和本题最接近的是 LeetCode 1248统计“优美子数组”数组里恰好有 k 个奇数的子数组。把奇数映射成 1、偶数映射成 0原题就变成了“恰好 k 个 1 的子数组”和 3899 几乎同一个解法非常适合放在同一天练。还有几道滑动窗口题虽然不是“恰好”型但用的是同一个窗口维护模板LeetCode 3无重复字符的最长子串单窗口加HashSetLeetCode 340至多 K 个不同字符的最长子串直接是“最多”型LeetCode 904水果成篮等价于至多 2 个不同字符的最长子数组LeetCode 76最小覆盖子串窗口内维护欠账计数逻辑稍复杂但骨架相似。把这五道题连起来刷一遍滑动窗口的“求最长、求最短、求数量”三种形态就齐了。5.2 一个能套用的滑动窗口模板我后来把这类计数滑窗模板固定成了五步定义窗口状态通常是计数器加一个“当前有多少种合法元素”的变量右指针每轮右移一位更新状态用while收缩左指针直到窗口重新满足约束每轮收缩完把“以右指针结尾的合法子数组数量”累加到答案如果题目要求“恰好”就构造f(x)函数做一次减法。这套模板对“最多”“至少”“恰好”三类约束都有用。区别只在于收缩条件和最后的统计方式。“最多”直接累加“至少”通常要配合欠账模型“恰好”就用减法归约。记熟练了面试遇到新题能快速定位到对应的变体。6. 个人刷题体会与后续扩展我个人的感受是LintCode 3899 的代码连三十行都不到难点全在思维转化。第一次做不出来太正常了我一开始也被“恰好”卡得很难受后来把“恰好等于最多减最多”这个套路背进脑子里同类题直接通了好几个。如果你正在准备面试建议把这题和 LeetCode 1248 放在同一天刷趁热打铁的效果比我这样隔了一周再遇到、重新推导一遍要强太多。还有个很笨但很有效的经验刷完 AC 只是第一步第二天把代码删掉重新写一遍能默写出来才算真会。我练滑动窗口专题时每道核心题都重复了三遍以上第一遍照着题解抄第二遍合上题解自己推边界第三遍模拟面试边讲边写。3899 就是靠这个方法从“会做”变成“肌肉记忆”的。如果你也把这道题吃透了接下来的扩展方向很明确。一个是看看 LeetCode 395“至少有 K 个重复字符的最长子串”那道题需要枚举字符种类数思路更宏观但底层还是这套窗口维护。另一个是去理解“上下界归约”思想在其他计数题里的应用比如前缀和计数、差分数组本质都是先把精确条件放宽成上界或下界再通过加减把精确区间夹出来。算法这东西模型见多了新题就都是老朋友换马甲。
