LeetCode 3859. 统计包含 K 个不同整数的子数组 - Rust 实现核心思路容斥原理 反向滑动窗口定义 f(lim) 为子数组中至少 lim 个不同整数且至少有 k 个不同整数出现次数 ≥ m 的子数组数量。由容斥原理- f(k)至少 k 个不同整数且至少 k 个 ≥ m 次- f(k1)至少 k1 个不同整数且至少 k 个 ≥ m 次- f(k) − f(k1) 恰好 k 个不同整数且这 k 个都 ≥ m 次滑动窗口维护不满足 f(lim) 条件的最小窗口 [l, r]则以 r 结尾、左端点在 [0, l−1] 的子数组都满足 f(lim)。rustuse std::collections::HashMap;impl Solution {pub fn count_subarrays(nums: Veci32, k: i32, m: i32) - i64 {let k k as usize;let m m as usize;// 容斥原理恰好 k 个不同元素且每个都 m 次Self::f(nums, k, m, k) - Self::f(nums, k 1, m, k)}/// 统计子数组中至少 lim 个不同元素且至少 k 个不同元素出现次数 mfn f(nums: [i32], lim: usize, m: usize, k: usize) - i64 {let mut cnt: HashMapi32, usize HashMap::new();let mut t 0usize; // 窗口中出现次数 m的不同元素个数let mut ans: i64 0;let mut l 0usize; // 左指针for x in nums {// 扩展右边界let c cnt.entry(x).or_insert(0);*c 1;if *c m {t 1;}// 收缩左边界当窗口 [l, r] 满足 f(lim) 条件时右移 l 直到不满足while cnt.len() lim t k {let y nums[l];let c cnt.get_mut(y).unwrap();if *c m {t - 1; // y 的出现次数从 m 降到 m-1}*c - 1;if *c 0 {cnt.remove(y); // y 完全移出窗口}l 1;}// 以当前 r 结尾、左端点在 [0, l-1] 的子数组都满足 f(lim)ans l as i64;}ans}}算法详解变量 类型 作用cnt HashMapi32, usize 窗口内各元素出现次数t usize 窗口中出现次数 ≥ m的不同元素个数l usize 左指针指向不满足 f(lim) 的最小窗口左边界lim usize 不同元素个数的下限滑动窗口过程1. 扩展右边界遍历 nums加入当前元素更新频次2. 维护窗口当窗口内不同元素个数 ≥ lim 且满足次数要求的元素 ≥ k 时窗口满足 f(lim) 条件持续收缩左边界直到不满足3. 统计贡献l 是不满足条件的最小左端点那么以 r 结尾、左端点在 [0, l−1] 的 l 个子数组都满足 f(lim)容斥原理- f(k) 包含恰好 k 个、恰好 k1 个、… 个不同元素且至少 k 个 ≥ m 次的子数组- f(k1) 包含恰好 k1 个、恰好 k2 个、… 个不同元素且至少 k 个 ≥ m 次的子数组- 两者相减恰好得到恰好 k 个不同元素且这 k 个都 ≥ m 次复杂度分析- 时间复杂度O(n)每个元素最多被加入和移出窗口各一次- 空间复杂度O(n)HashMap 存储窗口内元素频次示例验证输入nums [1,2,1,2,2], k 2, m 2- f(2) 统计至少 2 个不同且至少 2 个 ≥ 2 次贡献来自 [1,2,1,2] 和 [1,2,1,2,2]结果为 2- f(3) 统计至少 3 个不同且至少 2 个 ≥ 2 次无满足子数组结果为 0- 最终答案2 − 0 2