我在 LintCode 上刷数组专项时被 3899 这道题卡了很久public int subarraysWithDistinct(int[] nums, int k)题目要求统计恰好包含 k 个不同整数的连续子数组数量。这道题在 LeetCode 上的编号是 992属于滑动窗口板块的经典题也是一些后端 Java 面试手撕环节的高频题。题面短得不能再短但恰好两个字把第一次见它的人几乎全部绊倒。普通滑窗写出来只能回答最多 k 个不同一旦要求恰好 k 个左边界怎么动都别扭。这篇文章从暴力解讲起到 atMost 差分法的完整推导再给出可直接提交的 Java 实现最后把我踩过的坑和面试官常问的变体一起整理出来。无论你是准备 Java 面试还是单纯刷题这篇应该都能帮你少走弯路。1. 先读懂题为什么恰好 k 个不同能卡住一批人1.1 题面与数据约束LintCode 3899 的题面非常干净给定整数数组 nums 和一个整数 k返回 nums 中恰好包含 k 个不同整数的连续子数组个数。方法签名固定为public int subarraysWithDistinct(int[] nums, int k)在 LeetCode 上它还有另一个编号 992。常见的数据范围是1 ≤ nums.length ≤ 5 × 10^41 ≤ nums[i] ≤ nums.length0 ≤ k ≤ nums.length。数组长度能到五万值域被压到[1, n]内。这两个约束很重要后面代码里直接用数组做频次统计完全踩在这个约束上。先明确两个容易混淆的概念子数组必须连续子序列不要求连续不同整数看的是元素值去重后的个数而不是出现频次。例如[1,2,1,2]只有 1 和 2 两个不同整数虽然它们各出现了两次。1.2 先手动数一遍示例以官方示例nums [1,2,1,2,3]k 2为例答案是 7。手工枚举确实不难但枚举多了会发现一个规律以每个位置作为右端点合法的子数组数量并不均匀。按右端点分组的核对表如下右端点以它结尾的合法子数组数量nums[1] 2[1,2]1nums[2] 1[2,1]、[1,2,1]2nums[3] 2[1,2]、[2,1,2]、[1,2,1,2]3nums[4] 3[2,3]1合计 7。你会注意到一个关键现象对于固定的右端点所有合法起点连起来是一段连续区间不是东一个西一个。这个起点区间连续的观察正是滑动窗口高效解题的基础后面讲res right - left 1时会再回到这里。1.3 暴力枚举能过吗新手拿到题第一反应必然是枚举所有起点和终点再用 HashSet 统计窗口内不同数字的个数int count 0; for (int i 0; i n; i) { SetInteger set new HashSet(); for (int j i; j n; j) { set.add(nums[j]); if (set.size() k) { count; } else if (set.size() k) { break; } } }这个思路和冒泡排序有点像——逻辑简单谁都写得出来但复杂度是 O(n²)最坏情况下 n 5 × 10^4 时子数组总数约 1.25 × 10^9加上 HashSet 的开销必然超时。面试官看到这个版本会给点分但紧接着就会追问能不能 O(n)1.4 普通滑窗为什么搞不定恰好先想想最熟悉的滑窗题比如最长无重复字符子串或最多 k 个不同字符的子串。这类题有一个共同点约束是单侧的。窗口内不同整数超过 k就把左边界往右挪一直挪到合法为止窗口合法时直接累计所有以当前右端点结尾的子数组。整个过程只有一个不确定量窗口什么时候变非法。而恰好 k 个不同是个双侧约束既不能多于 k也不能少于 k。麻烦在于窗口可能不够 k你得等右指针继续扩大等它够了左边界又有一串可以移动的位置——因为重复元素的存在刚好 k 个的左边界不是一个点而是一段区间。比如[1,2,1,2]里以右端点 3 结尾、恰好包含 2 个不同整数的子数组是[1,2]、[2,1,2]、[1,2,1,2]起点分别可以是 1、2、0。想直接维护恰好状态需要同时记录区间的左右端点逻辑立刻复杂起来。所以大多数题解会绕一个弯先求最多 k 个再用差分把恰好 k 个算出来。这个套路值得单独拆开讲。2. 核心套路atMost 差分法把恰好变成两次最多2.1 一个简单的集合恒等式定义 f(k) 数组中不同整数个数不超过 k 的子数组数量。那么题目要求的恰好 k 个不同可以写成f(k) - f(k-1)为什么成立对任意子数组 s设它的不同整数个数为 d。如果 d ≤ k-1它在 f(k) 和 f(k-1) 里各被计一次相减后抵消如果 d k它只在 f(k) 里出现留下一次如果 d k两边都不出现。于是差恰好是所有 d k 的子数组。这个证明和具体实现无关纯集合论面试时两句话就能讲清楚。打个比方你想统计恰好考了 90 分的学生人数与其逐个查分数不如统计90 分及以下的人数减去89 分及以下的人数。统计对象没变逻辑却简单得多。先放宽再扣掉这个思想在滑动窗口计数题里几乎是万能钥匙LeetCode 1248恰好 k 个奇数的子数组也能用同一套思路。2.2 atMost 滑窗的实现与正确性接下来实现 f(k)也就是 atMost 版本。维护窗口[left, right]保证窗口内不同整数个数不超过 k然后每步累加。伪代码如下left 0distinct 0 for right 0..n-1: 把 nums[right] 计入频次若它是第一次出现distinct 当 distinct k: 把 nums[left] 移出频次 若它的频次降为 0distinct-- left 此时窗口合法 res right - left 1关键在于最后一行。固定右端点 right 时所有合法子数组的起点分布在[left, right]之间区间长度right - left 1就是本轮新增计数。为什么起点不可能小于 left因为 while 循环保证 left 已经推进到再往左一格就会超过 k 个不同整数的位置所以任何起点小于 left 的子数组不同整数个数一定大于 k。为什么区间内任意起点都合法因为子数组[s, right]s ≥ left是[left, right]的子集不同整数个数不可能超过整个窗口的不同整数个数必然 ≤ k。一头一尾卡死计数既不重也不漏。2.3 套回原题一次调用变成两次有了 atMost原题只剩一行public int subarraysWithDistinct(int[] nums, int k) { return atMost(nums, k) - atMost(nums, k - 1); }注意第二项传入的是k - 1。把最多 k 个不同的子数组数出来扣掉最多 k-1 个不同的剩下的就是恰好 k 个不同的。实现上多跑一遍滑窗常数翻倍但渐进复杂度仍然是 O(n)面试官不会因此扣分反而会觉得你思路清楚。3. Java 实现与复杂度账本3.1 完整可提交的代码基于题目给的数据范围nums[i]在[1, n]内直接用数组做频次表最快public class Solution { public int subarraysWithDistinct(int[] nums, int k) { if (nums null || nums.length 0 || k 0) { return 0; } return atMost(nums, k) - atMost(nums, k - 1); } private int atMost(int[] nums, int k) { int n nums.length; int[] freq new int[n 1]; int left 0; int distinct 0; int res 0; for (int right 0; right n; right) { if (freq[nums[right]] 0) { distinct; } freq[nums[right]]; while (distinct k) { freq[nums[left]]--; if (freq[nums[left]] 0) { distinct--; } left; } res right - left 1; } return res; } }这个版本我实测过直接可以提交。需要留意的是 LintCode 的类名和 import 要求以平台为准核心方法签名保持不变即可。3.2 数组频次与 HashMap 怎么选数组做法依赖一个前提nums[i]的值都在[0, n]内freq 下标才不会越界。LeetCode 992 保证了1 ≤ nums[i] ≤ n所以int[n1]安全。如果题目不保证值域比如出现负数或超大整数直接用nums[i]当下标会抛ArrayIndexOutOfBoundsException。两个替代方案用HashMapInteger, Integer存频次优点是通用缺点是自动装箱、拆箱和哈希计算有额外开销先扫一遍找出最小值和最大值用nums[i] - min做偏移下标int min Integer.MAX_VALUE, max Integer.MIN_VALUE; for (int v : nums) { min Math.min(min, v); max Math.max(max, v); } int[] freq new int[max - min 1]; // 访问时写成 freq[nums[right] - min]偏移技巧在笔试环境很实用既保留数组的 O(1) 访问速度又不依赖值域恰好是[1, n]。提示提交前先看题目 Constraints 段落。约束里写了值域你就老老实实用数组没写就用 HashMap不要赌测试数据。3.3 时间与空间复杂度时间上right 指针总共前进 n 步left 指针虽然在 while 里可能连续移动但每个位置最多被 left 经过一次整体均摊 O(n)。两次 atMost 调用意味着最多 2n 次主循环常数翻倍量级不变。空间上freq 数组是 O(n)换 HashMap 的话理论最坏也是 O(n)实际窗口被 k 限制通常远小于 n。还有一个容易被忽略的数值细节返回值类型。n 5 × 10^4 时子数组总数上限是n(n1)/2 1,250,025,000小于 int 上限2,147,483,647所以方法签名敢用 int。如果约束改成 n 10^5总数会到 5 × 10^9int 直接溢出这时要么改用 long要么在累加时防溢出。面试时可以主动提一句说明你考虑过数值边界。3.4 边界条件的处理代码里写了三个提前返回数组为 null、数组长度 0、k ≤ 0。重点解释 k 0非空数组的任何子数组至少包含 1 个不同整数所以答案是 0直接返回最干净。如果不提前返回atMost(nums, 0)会得到 0而atMost(nums, -1)需要在函数内部处理负数绕一圈结果碰巧也对但代码会让人困惑。k 大于 n 的情况同样可以直接返回 0因为整个数组的不同整数都不可能超过 n 个。这些边界条件自己刷题时容易忽略但面试官特别喜欢拿来试探。4. 面试追问一个套路派生出一整类问题4.1 变体一最多 k 个不同整数的子数组个数原题改成最多 k 个答案直接就是atMost(nums, k)一行代码不用改。再比如 LeetCode 340 求最多 k 个不同字符的最长子串只需要把累加式res right - left 1换成res Math.max(res, right - left 1)。同一个滑窗骨架换一行统计方式解决的是完全不同的问题。这也是面试官喜欢从这道题展开的原因——把 atMost 理解透等于同时会了好几道题。4.2 变体二恰好 k 个不同整数的最短和最长子数组最短版本可以基于 atMost 滑窗继续做while 保证窗口不超过 k 个不同之后如果distinct k再内层 while 把左侧重复元素挤掉即当freq[nums[left]] 1时不断 left。此时窗口就是以 right 结尾、恰好 k 个不同的最短窗口更新最短长度即可。最长版本稍绕需要两个左指针同时维护。记 L1 是满足最多 k 个不同的最小左边界L2 是满足最多 k-1 个不同的最小左边界。因为约束更紧L2 ≥ L1。固定右端点 right 时起点在[L1, L2-1]内的子数组恰好有 k 个不同最长候选长度是right - L1 1并且仅当 L2 L1 时成立。这个双左指针写法在讨论区常被称作 elongated window 技巧面试能现场写出来绝对是加分项。4.3 变体三条件换一下套到 1248 题LeetCode 1248 统计恰好 k 个奇数的子数组本质和这道题一模一样把不同整数个数换成奇数个数即可。奇数个数可以用前缀和实现也可以用atMost(k) - atMost(k-1)其中 atMost 统计不超过 k 个奇数的子数组判断条件从首次出现变成nums[right] % 2 1。这种跨题复用能力是刷题最值得沉淀的部分不要背题要背问题结构。4.4 面试官追问两次 atMost 是不是浪费有人会质疑明明可以一个滑窗搞定为什么调用两次核心答案渐进复杂度不变都是 O(n)代码清晰度大幅提升。如果面试官较真常数可以补一句可以把两次 atMost 合并成一次双指针遍历用 L1、L2 两个左界同时推进一次循环就算出 f(k) 和 f(k-1)然后简要给出思路。大多数面试官到这里只会点头不会真让你写完。真正需要避免的是交出 O(n²) 的暴力解那才是硬伤。5. 提交过程中的踩坑记录与调试套路5.1 坑一while 写成 if窗口收缩不彻底这是我见过最多的错法。当distinct k时如果只收缩一次nums[left]的频次减完可能仍然大于 0distinct 根本没有下降窗口依旧非法下一轮统计就会把多余的子数组算进去。必须用 while一直收缩到distinct ≤ k。排查时可以临时打印 left、right、distinct、freq 数组一眼就能看出窗口是否真正收缩到位。5.2 坑二freq 数组下标越界直接用nums[i]作为 freq 下标必须确认值域。LeetCode 992 固定了值域问题不大但 LintCode 某些变体或你自己构造测试数据时负数、0、超过 n 的值都可能出现。应对方法是先读 Constraints再用偏移量或 HashMap。我在 3.2 给的偏移技巧处理这类问题很顺手。5.3 坑三k 的边界导致 atMost 收到负数subarraysWithDistinct(nums, 0)时第二项是atMost(nums, -1)。如果 atMost 内部没有对 k 0 做防护distinct -1恒成立left 会一路推到 right1res 始终加 0结果碰巧没错但行为非常诡异。我在 3.1 里做了入口拦截这种边界问题从源头避免。5.4 坑四不写对拍器错了不知道错在哪刷这类计数题我的习惯是写一个 O(n²) 的暴力版本再用随机数组对拍。暴力版就是 1.3 节的 HashSet 枚举对拍代码大致如下static int brute(int[] nums, int k) { int n nums.length, count 0; for (int i 0; i n; i) { SetInteger set new HashSet(); for (int j i; j n; j) { set.add(nums[j]); if (set.size() k) count; else if (set.size() k) break; } } return count; } public static void main(String[] args) { Random rand new Random(); for (int t 0; t 10000; t) { int n rand.nextInt(15) 1; int[] nums new int[n]; for (int i 0; i n; i) nums[i] rand.nextInt(5) 1; int k rand.nextInt(n 1); int a new Solution().subarraysWithDistinct(nums, k); int b brute(nums, k); if (a ! b) { System.out.println(Arrays.toString(nums) k k got a expected b); break; } } System.out.println(done); }小数据、小值域、几千轮随机测试跑下来正确性基本能拍死。别以为暴力对拍浪费时间它能把注意力集中在算法思路上而不是在手工枚举里反复找错。5.5 建议的入门用例调试代码时先用几组有代表性的小用例验证输入k预期说明[1,1,1]16所有 6 个子数组都只有 1 个不同整数[1,2]21只有 [1,2][1,2,1]13[1]、[2]、[1][1,2,1]23[1,2]、[2,1]、[1,2,1][1,2,1,2,3]27官方示例这些用例能覆盖 k 的最小值、窗口收缩、重复元素密集等典型场景。跑完这些再上随机对拍基本不会有漏网之鱼。最后分享一个我的体会看到恰好 k 个的计数题第一反应先写 atMost再相减比硬写一个恰好滑窗省力得多也不容易错。刷熟这道题之后1248、713 这类题目基本就是换皮。你可以把 atMost 差分当成一个固定套路存在脑子里遇到恰好就调用遇到最多就直接用这才是在面试里真正值钱的部分。