双指针专题(十)：恰好等于的困境——「K 个不同整数的子数组」

场景想象：你是一个统计员，要把数组切成很多段。 老板要求：每一段里必须恰好包含K种不同的数字。

• 比如[1, 2, 1, 2, 3],K=2。

• [1, 2, 1, 2]是符合的（只有 1 和 2 两种）。

• [1, 2, 1, 2, 3]不符合（有 3 种）。

• [1]不符合（只有 1 种）。

难点：滑动窗口最擅长处理的是“最多 K 个”（类似《水果成篮》）或者“至少 K 个”。 对于“恰好 K 个”，窗口的左边界很难确定。因为“恰好 2 个”的情况可能有很多种（比如[1, 2]和[1, 2, 1]都是），左指针到底缩到哪里才算完呢？

力扣 992. K 个不同整数的子数组

https://leetcode.cn/problems/subarrays-with-k-different-integers/

题目分析：

• 输入：数组nums，整数k。

• 输出：满足条件的子数组数量。

核心思维：恰好(K) = 最多(K) - 最多(K-1)

这是一个非常经典的集合论思想：

• 最多 K 种：包含“恰好 1 种”、“恰好 2 种” ... “恰好 K 种”。

• 最多 K-1 种：包含“恰好 1 种” ... “恰好 K-1 种”。

如果你把这两个集合相减，剩下的不就是“恰好 K 种”了吗？

转化优势：求“最多包含 K 种整数的子数组数量”非常简单，就是标准的滑动窗口（和《水果成篮》一模一样）。 我们只需要写一个 helper 函数atMost(k)，然后调用两次即可：return atMost(k) - atMost(k - 1);

atMost(k)的计数逻辑：当窗口[left, right]满足“最多 K 种”时，以nums[right]结尾的、满足条件的子数组有多少个？ 答案是right - left + 1个。

• 比如[1, 2](K=2)。以 2 结尾的子数组有[2]和[1, 2]，共 2 个。

• 这个公式累加起来，就是总数。

代码实现 (JavaScript)

JavaScript

/** * @param {number[]} nums * @param {number} k * @return {number} */ var subarraysWithKDistinct = function(nums, k) { // 核心公式：恰好 K = 最多 K - 最多 K-1 return atMost(nums, k) - atMost(nums, k - 1); }; /** * 辅助函数：求最多包含 k 种不同整数的子数组数量 * 这就是标准的滑动窗口模板（类似水果成篮） */ function atMost(nums, k) { let left = 0; let right = 0; let count = 0; // 记录符合条件的子数组总数 let distinctCount = 0; // 当前窗口有多少种不同的数 // 使用数组代替 Map 统计频率，性能会好很多（题目提示 nums[i] <= 20000） // 如果没有范围限制，可以用 Map const freq = new Array(nums.length + 1).fill(0); while (right < nums.length) { // --- 进窗口 --- if (freq[nums[right]] === 0) { distinctCount++; } freq[nums[right]]++; right++; // --- 出窗口 --- // 如果种类超过 k，必须收缩 while (distinctCount > k) { freq[nums[left]]--; if (freq[nums[left]] === 0) { distinctCount--; } left++; } // --- 核心累加 --- // 此时窗口 [left, right-1] 内的种类 <= k // 那么以 right-1 结尾的子数组数量就是窗口长度 count += right - left; } return count; }

深度模拟

假设nums = [1, 2, 1, 2, 3],k = 2。

1. 计算atMost(2):

   • [1]-> +1

   • [1, 2]-> +2 (子数组:2,1,2)

   • [1, 2, 1]-> +3 (子数组:1,2,1,1,2,1)

   • [1, 2, 1, 2]-> +4

   • 遇到 3 (种类变3) -> 缩左边直到[2, 3]-> +2

   • 总数 A

2. 计算atMost(1):

   • [1]-> +1

   • 遇到 2 (种类变2) -> 缩左边直到[2]-> +1

   • 遇到 1 (种类变2) -> 缩左边直到[1]-> +1

   • ...

   • 总数 B

3. 结果：A - B就是我们要的答案。

总结

恭喜你！🎉 到这里，我们的双指针与滑动窗口专题就彻底结业了！

我们从最简单的快慢指针（移除元素）开始，一路打怪升级，经过了对撞指针（三数之和）、不定长窗口（最小覆盖子串），最后攻克了单调队列（滑动窗口最大值）和数学转换（K个不同整数）。