09 多类别元素与恰好 K 型窗口：高阶滑动窗口技法

多类别元素与恰好 K 型窗口：高阶滑动窗口技法

摘要

前几篇讨论的滑动窗口约束大多是”窗口内满足某个不等式”（最多 K 个不同元素、和不超过 limit 等），本篇攻克更难的变体：“恰好 K”型约束。“窗口内恰好有 K 个不同整数”不是单调性约束，不能直接套用前几篇的收缩模板——但可以用一个漂亮的数学变换将其转化为两个”最多 K”问题之差。

本篇通过 LeetCode 992（K 个不同整数的子数组，恰好 K 转化的典型）、LeetCode 1234（替换子串得到平衡字符串，多类别均等分配）、LeetCode 2461（长度为 K 的子数组中的最大和，多类别元素互斥）三道题，系统讲解”恰好 K”转化、多类别计数器、以及在 LeetCode Hard 级别题目中的组合应用。

---

第 1 章 “恰好 K” 型问题的核心困难

1.1 为什么”恰好 K”不能直接用滑动窗口

回顾第 05 篇”至多 K 种不同元素”的模板：窗口不合法时（distinct > k），持续收缩左指针，直到合法；每步更新最长长度。

这是单调性的体现：扩大窗口，不同元素数可能增加；收缩窗口，不同元素数只会减少或不变。

但”恰好 K 种不同元素”不是单调约束：扩大窗口，不同元素数增加；但继续扩大，不同元素数还在增加，超过 K 了！而收缩窗口，不同元素数减少，又可能低于 K 了！窗口大小和不同元素数之间没有稳定的单调关系可以利用。

1.2 恰好 K 的数学变换

$\text{恰好 K 种}=\text{至多 K 种}-\text{至多 K-1 种}$

证明：设 f(k) 表示”至多 K 种不同元素的子数组数量”。

• f(k) 包含”恰好 0 种”、“恰好 1 种”、…、“恰好 K 种”的子数组
• f(k-1) 包含”恰好 0 种”、“恰好 1 种”、…、“恰好 K-1 种”的子数组
• f(k) - f(k-1) = “恰好 K 种”的子数组数量

这个转化把不可直接处理的”恰好”问题，拆分为两个可以用滑动窗口处理的”至多”问题。

// "恰好 K" = "至多 K" - "至多 K-1"
int exactlyK(int[] nums, int k) {
    return atMostK(nums, k) - atMostK(nums, k - 1);
}

1.3 “至多 K 种”子数组数量的标准计算

第 05 篇的滑动窗口只求最长长度，这里需要求所有满足条件的子数组数量。

对于以 right 为右端点、最长合法左端点为 left 的窗口，以 right 为右端点的满足”至多 K 种”的子数组有 right - left + 1 个（从 [left, right] 到 [right, right]）。

int atMostK(int[] nums, int k) {
    int left = 0, count = 0;
    Map<Integer, Integer> freq = new HashMap<>();
 
    for (int right = 0; right < nums.length; right++) {
        // 进窗
        freq.merge(nums[right], 1, Integer::sum);
 
        // 收缩：当不同元素数超过 k 时
        while (freq.size() > k) {
            int out = nums[left++];
            if (freq.merge(out, -1, Integer::sum) == 0) freq.remove(out);
        }
 
        // 以 right 为右端点的合法子数组数量
        count += right - left + 1;
    }
    return count;
}

---

第 2 章 LeetCode 992：K 个不同整数的子数组

2.1 题目

LeetCode 992 - Subarrays with K Different Integers（困难）

给定一个正整数数组 nums 和一个整数 k，返回 nums 中好子数组的数目。好子数组中恰好有 k 个不同的整数。

输入：nums = [1,2,1,2,3], k = 2
输出：7
解释：恰好有 2 个不同整数的子数组：[1,2],[2,1],[1,2],[2,3],[1,2,1],[2,1,2],[1,2,1,2]

输入：nums = [1,2,1,3,4], k = 3
输出：3
解释：[1,2,1,3],[2,1,3],[1,3,4]

2.2 完整实现

public int subarraysWithKDistinct(int[] nums, int k) {
    return atMostK(nums, k) - atMostK(nums, k - 1);
}
 
private int atMostK(int[] nums, int k) {
    int left = 0, count = 0;
    Map<Integer, Integer> freq = new HashMap<>();
 
    for (int right = 0; right < nums.length; right++) {
        // 进窗：记录 nums[right] 的频率
        freq.merge(nums[right], 1, Integer::sum);
 
        // 收缩：不同元素数超过 k，移动左指针
        while (freq.size() > k) {
            int out = nums[left++];
            // 频率减一；若降为 0，说明该元素已完全离窗，移除键
            if (freq.merge(out, -1, Integer::sum) == 0) {
                freq.remove(out);
            }
        }
 
        // 以 right 为右端点的"至多 K 种"子数组数量
        count += right - left + 1;
    }
    return count;
}

时间复杂度：$O(n)$（atMostK 调用两次，各 $O(n)$） 空间复杂度：$O(k)$（哈希表大小不超过 $k+1$）

2.3 逐步追踪 atMostK([1,2,1,2,3], 2)

left=0
right=0: freq={1:1}, size=1<=2, count += 0-0+1=1 → count=1
right=1: freq={1:1,2:1}, size=2<=2, count += 1-0+1=2 → count=3
right=2: freq={1:2,2:1}, size=2<=2, count += 2-0+1=3 → count=6
right=3: freq={1:2,2:2}, size=2<=2, count += 3-0+1=4 → count=10
right=4: freq={1:2,2:2,3:1}, size=3>2
  出窗 nums[0]=1: freq={1:1,2:2,3:1}, size=3>2, left=1
  出窗 nums[1]=2: freq={1:1,2:1,3:1}, size=3>2, left=2
  出窗 nums[2]=1: freq={2:1,3:1},     size=2<=2, left=3
  count += 4-3+1=2 → count=12
atMostK(nums, 2) = 12

atMostK([1,2,1,2,3], 1):
right=0: freq={1:1}, count=1
right=1: freq={1:1,2:1}, size=2>1 → 出窗1,left=1, freq={2:1}, count += 1-1+1=1 → count=2
right=2: freq={2:1,1:1}, size=2>1 → 出窗2,left=2, freq={1:1}, count += 2-2+1=1 → count=3
right=3: freq={1:1,2:1}, size=2>1 → 出窗1,left=3, freq={2:1}, count += 3-3+1=1 → count=4
right=4: freq={2:1,3:1}, size=2>1 → 出窗2,left=4, freq={3:1}, count += 4-4+1=1 → count=5
atMostK(nums, 1) = 5

答案 = 12 - 5 = 7 ✓

2.4 转化思维的普遍性

“恰好 K” = “至多 K” - “至多 K-1” 这个技巧在多种题型中通用：

• 不同整数恰好 K 个（LeetCode 992）
• 奇数个数恰好 K 个（LeetCode 1248，也可用此法）
• 子数组和恰好等于 K（实际上更适合前缀和哈希，但”恰好 K”转化也可用于全正数版本）

核心思想："恰好" 的转化

当约束是”恰好等于 K”时，几乎总是可以用”至多 K” - “至多 K-1”来转化为两个单调约束。这是面试中处理”恰好型滑动窗口”的标准思路。

---

第 3 章 LeetCode 1234：替换子串得到平衡字符串

3.1 题目

LeetCode 1234 - Replace the Substring for Balanced String（中等）

有一个只含有 'Q', 'W', 'E', 'R' 四种字符的字符串 s，且每种字符的出现次数相同。

你可以替换一个子串（连续的字符），使得字符串变得平衡（每种字符恰好出现 n/4 次）。求需要替换的子串的最小长度。如果字符串已经平衡，返回 0。

输入：s = "QWER"
输出：0（已经平衡）

输入：s = "QQWE"
输出：1（替换一个 'Q' 为 'R'）

输入：s = "QQQW"
输出：2（替换 "QQ" 为 "ER" 或 "RE"）

输入：s = "QQQQ"
输出：3（替换 "QQQ" 为 "WER"）

3.2 反向思维：固定窗口外，计算窗口内

关键观察：替换的子串是连续的，替换操作可以把窗口内的任意字符变成任意字符。因此，只要窗口外的字符中，每种字符出现次数都 ≤ n/4，我们就可以通过替换窗口内的字符使整个字符串平衡（把窗口外多余的字符”覆盖”到窗口内，把窗口内需要补充的字符替换到）。

等价条件：设 target = n / 4，count[c] 为字符 c 在整个字符串中的频率。当窗口为 [left, right] 时，窗口外字符 c 的频率 = count[c] - window_count[c]。

合法条件：对所有字符 c，count[c] - window_count[c] <= target，即 window_count[c] >= count[c] - target。

换句话说：窗口内必须包含”足够多”的各类字符——那些在窗口外超出 target 的字符，必须有足够数量在窗口内（以便通过替换消化掉）。

3.3 可变窗口最小长度实现

public int balancedString(String s) {
    int n = s.length();
    int target = n / 4;
    int[] count = new int[128];  // 整个字符串中各字符的频率
    for (char c : s.toCharArray()) count[c]++;
 
    // 如果已经平衡，直接返回 0
    if (count['Q'] == target && count['W'] == target
            && count['E'] == target && count['R'] == target) {
        return 0;
    }
 
    int left = 0, minLen = n;
    int[] window = new int[128];  // 窗口内各字符的频率
 
    for (int right = 0; right < n; right++) {
        window[s.charAt(right)]++;
 
        // 收缩：当窗口合法时（窗口外每种字符 <= target），尝试缩小窗口
        while (left <= right && isValid(count, window, target)) {
            minLen = Math.min(minLen, right - left + 1);
            window[s.charAt(left)]--;
            left++;
        }
    }
    return minLen;
}
 
private boolean isValid(int[] count, int[] window, int target) {
    // 检查窗口外的每种字符都不超过 target
    return count['Q'] - window['Q'] <= target
        && count['W'] - window['W'] <= target
        && count['E'] - window['E'] <= target
        && count['R'] - window['R'] <= target;
}

时间复杂度：$O(n)$（每个字符最多进出窗口一次，isValid 是 $O(1)$） 空间复杂度：$O(1)$

3.4 收缩顺序与最短窗口

注意这里的收缩模式是**第 03 篇”最短窗口”**的模式：先扩大到合法，然后在合法时持续收缩并更新答案。与最长窗口（先收缩到合法再更新答案）方向相反。

第 03 篇总结的规律在这里再次验证：

• 求最短合法窗口：合法时收缩（先收缩后检查），答案在收缩前更新
• 求最长合法窗口：不合法时收缩，答案在每步更新

题目分类小结

LeetCode 1234 是一道包装了”固定和均等分配”语义的最短可变窗口题。解题关键是把”替换操作”转化为”窗口合法性”的等价条件，把多类别的约束折叠成 4 个独立检查。

---

第 4 章 LeetCode 2461：长度为 K 的子数组中的最大和（元素互斥）

4.1 题目

LeetCode 2461 - Maximum Sum of Distinct Subarrays With Length K（中等）

给你一个整数数组 nums 和一个整数 k。找出 nums 中长度为 k 的、具有不同元素（窗口内所有元素各不相同）的子数组，并返回其最大元素和。如果不存在合适的子数组，返回 0。

输入：nums = [1,5,4,2,9,9,9], k = 3
输出：15
解释：长度为 3 的不同元素子数组：[1,5,4]（和10）,[5,4,2]（和11）,[4,2,9]（和15）,[2,9,9]（不满足），[9,9,9]（不满足）。最大和 15。

输入：nums = [4,4,4], k = 3
输出：0（没有不同元素的长度3子数组）

4.2 固定窗口 + 多类别计数

这是一道固定窗口题，条件是”窗口内所有元素不同”（即 distinct 数量 = k）。

维护：

• windowSum：当前窗口元素和
• freq：当前窗口内各元素的出现次数（判断是否有重复）

public long maximumSubarraySum(int[] nums, int k) {
    int n = nums.length;
    long maxSum = 0, windowSum = 0;
    Map<Integer, Integer> freq = new HashMap<>();
 
    for (int right = 0; right < n; right++) {
        // 进窗
        int in = nums[right];
        freq.merge(in, 1, Integer::sum);
        windowSum += in;
 
        // 出窗（固定窗口：right >= k 时移除最左元素）
        if (right >= k) {
            int out = nums[right - k];
            windowSum -= out;
            if (freq.merge(out, -1, Integer::sum) == 0) freq.remove(out);
        }
 
        // 检查：窗口已满 且 窗口内所有元素不同（freq.size() == k）
        if (right >= k - 1 && freq.size() == k) {
            maxSum = Math.max(maxSum, windowSum);
        }
    }
    return maxSum;
}

时间复杂度：$O(n)$ 空间复杂度：$O(k)$

4.3 freq.size() == k 的精妙

用哈希表大小（freq.size()）来判断窗口内是否所有元素都不同，比维护一个 distinct 计数器更简洁：

• freq.size() == k：窗口内 k 个元素对应 k 个不同的键，说明没有重复
• freq.size() < k：有重复元素（某些键有频率 > 1）

这里不能直接用 freq.size() < k 就判断不合法然后收缩——因为是固定窗口，不需要也不允许收缩。只需要在窗口满时检查条件，不满足就跳过。

4.4 对比：固定窗口 vs 可变窗口的处理不同元素

题目	窗口类型	不同元素的处理
LeetCode 2461（本题）	固定 k	进出对称，末尾判断 freq.size() == k
LeetCode 3（无重复最长子串）	可变，求最长	收缩到 freq.size() <= 1（每个元素至多一个）
LeetCode 904（水果成篮）	可变，求最长	收缩到 freq.size() <= 2
LeetCode 992（恰好 K 种）	可变，求数量	atMostK - atMostK(k-1)

不同元素的约束可以出现在固定或可变窗口中，处理方式因窗口类型而异。

---

第 5 章 高阶组合技法

5.1 嵌套滑动窗口

某些题目需要在滑动窗口内部再维护一个结构，构成嵌套。例如：

• LeetCode 480（滑动窗口中位数）：固定窗口 + 两个堆（维护中位数），时间复杂度 $O(n\log k)$
• LeetCode 76（最小覆盖子串）：可变窗口 + 哈希（already covered in 03）

这类题目的关键是分清”窗口的移动逻辑”和”窗口内数据结构的维护逻辑”，分别实现，再组合。

5.2 多条件组合的窗口合法性

本篇的 1234 题展示了多类别（4 种字符）同时约束的情形。处理多条件合法性的通用思路：

1. 将多个约束折叠为一个布尔判断（如 isValid 函数）：适合条件个数固定（如 4 种字符）
2. 维护”不合法条件数 violated”计数器：当任何一个约束不合法时 violated++，合法时 violated--，当 violated == 0 时整体合法。适合条件个数动态或较多

第 02 篇的 match 计数器就是这种思路：match 记录已经满足的字符种类数，match == distinct 时整体合法。

5.3 “恰好 K” 转化的完整通用模板

// 通用模板：恰好 K 个满足某条件的子数组数量
// condition(x): 元素 x 是否满足条件（如：是奇数、是某种类型）
// "恰好 K 个满足 condition 的元素" = "至多 K 个" - "至多 K-1 个"
 
int atMostKSatisfying(int[] nums, int k) {
    int left = 0, count = 0;
    int satisfiedInWindow = 0;  // 窗口内满足条件的元素个数
 
    for (int right = 0; right < nums.length; right++) {
        if (condition(nums[right])) satisfiedInWindow++;
        while (satisfiedInWindow > k) {
            if (condition(nums[left])) satisfiedInWindow--;
            left++;
        }
        count += right - left + 1;
    }
    return count;
}
 
int exactlyK(int[] nums, int k) {
    return atMostKSatisfying(nums, k) - atMostKSatisfying(nums, k - 1);
}

这个模板适用于：

• “恰好 K 个奇数”（LeetCode 1248）
• “恰好 K 种不同整数”（LeetCode 992）
• “恰好 K 个零”
• “恰好 K 个满足某条件的元素”

---

本篇总结

本篇系统讲解了”恰好 K”型窗口和多类别元素约束：

1. “恰好 K” = “至多 K” - “至多 K-1”：把不可直接处理的精确约束转化为两个单调约束，是面试压轴题的标准技法
2. LeetCode 992（K 个不同整数）：恰好 K 转化的经典题，atMostK 实现中的计数模式
3. LeetCode 1234（平衡字符串）：多类别约束 + 最短可变窗口，isValid 折叠多条件
4. LeetCode 2461（不同元素最大和）：固定窗口中用 freq.size() 判断不同元素约束

核心区分：

• 不等式约束（≤ 或 ≥）→ 直接滑动窗口，单次扫描
• 精确等于 K →“恰好 K” = “至多 K” - “至多 K-1”，两次扫描

---

参考与延伸

• 05 同向双指针统一视角：快慢指针与滑动窗口的辩证关系 — “至多 K 种”的基础框架
• 08 前缀和与滑动窗口的思想融合：子数组求和类问题 — “和恰好为 K”的前缀和哈希解法
• 10 滑动窗口综合通关：面试高频模式总结与难题攻破 — 所有技法的模式总结与决策树

---

课后练习

LeetCode 2537 - 统计好子数组的数目（中等）

如果一个数组中至少有 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j]，则称该数组为好数组。给你整数数组 nums 和整数 k，返回好子数组的数目。

提示：进窗时 nums[right] 的当前频率为 freq，加入后窗口内的新增配对数 pairs += freq；收缩时 pairs -= freq[nums[left]] - 1，然后 freq[nums[left]]--。合法条件 pairs >= k，用最短窗口思路计数：count += left（以 right 为右端点，左端点在 [0, left-1] 范围内的子数组均合法）。