企业官网建设流程全解析

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`