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 实现

```java
class 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) {
        Map<Integer, Integer> cnt = new HashMap<>();
        long ans = 0;
        int l = 0;
        int t = 0; // 记录当前窗口中有多少个元素的出现次数 >= m

        for (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(k+1)`：至多 k+1 个不同元素，每个都 ≥ m 次  
- 两者相减 = 恰好 k 个不同元素，每个都 ≥ m 次

复杂度分析

- 时间复杂度：O(n)，每个元素最多被加入和移出窗口各一次
- 空间复杂度：O(n)，HashMap 存储窗口中的元素计数

示例验证

示例 1：`nums = [1,2,1,2,2], k = 2, m = 2`
- 有效子数组：`[1,2,1,2]` 和 `[1,2,1,2,2]`
- 输出：`2`

示例 2：`nums = [3,1,2,4], k = 2, m = 1`
- 有效子数组：`[3,1]`, `[1,2]`, `[2,4]`
- 输出：`3`