LeetCode 3859 - Count Subarrays With K Distinct Integers题目描述给定整数数组 nums 和两个整数 k、m返回满足以下条件的子数组数量- 子数组中恰好包含 k 个不同的整数- 子数组中每个不同的整数至少出现 m 次核心思路双滑窗 容斥原理这道题是经典题 [992. Subarrays with K Different Integers](https://leetcode.com/problems/subarrays-with-k-different-integers/) 的扩展增加了每个不同元素至少出现 m 次的限制。关键洞察使用容斥原理恰好 k 个不同元素 至多 k 个不同元素 - 至多 k-1 个不同元素对于至多 lim 个不同元素且每个都至少出现 m 次的子数组计数可以用双指针滑动窗口解决。Java 实现javaclass Solution {private int[] nums;private int k;private int m;public long countSubarrays(int[] nums, int k, int m) {this.nums nums;this.k k;this.m m;// 容斥原理恰好 k 个 至多 k 个 - 至多 k-1 个return f(k) - f(k 1);}/*** 统计至多 lim 个不同元素且每个不同元素都至少出现 m 次的子数组数量* 注意这里统计的是每个出现的不同元素都满足至少 m 次的子数组*/private long f(int lim) {MapInteger, Integer cnt new HashMap();long ans 0;int l 0;int t 0; // 记录当前窗口中有多少个元素的出现次数 mfor (int x : nums) {// 扩展右边界if (cnt.merge(x, 1, Integer::sum) m) {t; // x 的出现次数刚好达到 m}// 收缩左边界当不同元素个数超过 lim或满足 m 的元素个数超过 k 时// 注意这里 t k 是因为我们要保证每个不同元素都至少出现 m 次while (cnt.size() lim t k) {int y nums[l];int cur cnt.merge(y, -1, Integer::sum);if (cur m - 1) {--t; // y 的出现次数从 m 降到 m-1}if (cur 0) {cnt.remove(y);}}// 以当前右端点结尾左端点可以在 [0, l] 范围内的子数组都满足条件ans l;}return ans;}}算法解释变量 含义cnt HashMap记录窗口中每个元素的出现次数l 左指针指向满足条件的窗口的最左边界t 当前窗口中出现次数 ≥ m的不同元素个数lim 允许的不同元素个数上限滑动窗口过程1. 扩展右边界right 向右移动加入新元素更新计数2. 维护窗口当窗口中不同元素个数 ≥ lim 且满足次数要求的元素个数 ≥ k 时收缩左边界3. 计数对于每个 right所有以 right 结尾、左端点在 [0, l] 的子数组都满足至多 lim 个不同元素且每个都 ≥ m 次容斥原理- f(k)至多 k 个不同元素每个都 ≥ m 次- f(k1)至多 k1 个不同元素每个都 ≥ m 次- 两者相减 恰好 k 个不同元素每个都 ≥ m 次复杂度分析- 时间复杂度O(n)每个元素最多被加入和移出窗口各一次- 空间复杂度O(n)HashMap 存储窗口中的元素计数示例验证示例 1nums [1,2,1,2,2], k 2, m 2- 有效子数组[1,2,1,2] 和 [1,2,1,2,2]- 输出2示例 2nums [3,1,2,4], k 2, m 1- 有效子数组[3,1], [1,2], [2,4]- 输出3