LeetCode 3859. 统计包含 K 个不同整数的子数组 - Rust 实现

核心思路：容斥原理 + 反向滑动窗口

定义 `f(lim)` 为：子数组中至少 `lim` 个不同整数，且至少有 `k` 个不同整数出现次数 ≥ `m` 的子数组数量。

由容斥原理：
- `f(k)`：至少 `k` 个不同整数，且至少 `k` 个 ≥ `m` 次
- `f(k+1)`：至少 `k+1` 个不同整数，且至少 `k` 个 ≥ `m` 次
- `f(k) − f(k+1)` = 恰好 `k` 个不同整数，且这 `k` 个都 ≥ `m` 次

滑动窗口维护不满足 `f(lim)` 条件的最小窗口 `[l, r]`，则以 `r` 结尾、左端点在 `[0, l−1]` 的子数组都满足 `f(lim)`。

```rust
use std::collections::HashMap;

impl Solution {
    pub fn count_subarrays(nums: Vec<i32>, 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 个不同元素出现次数 >= m
    fn f(nums: &[i32], lim: usize, m: usize, k: usize) -> i64 {
        let mut cnt: HashMap<i32, 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`    `HashMap<i32, 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` 个、恰好 `k+1` 个、… 个不同元素且至少 `k` 个 ≥ `m` 次的子数组
- `f(k+1)` 包含：恰好 `k+1` 个、恰好 `k+2` 个、… 个不同元素且至少 `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`