992. K 个不同整数的子数组
给定一个正整数数组 nums和一个整数 k ，返回 num 中 「好子数组」 的数目。
如果 nums 的某个子数组中不同整数的个数恰好为 k，则称 nums 的这个连续、不一定不同的子数组为 「好子数组 」。
例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。
子数组 是数组的 连续 部分。
示例 1：
输入：nums = [1,2,1,2,3], k = 2
输出：7
解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1],[1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
示例 2：
输入：nums = [1,2,1,3,4], k = 3
输出：3
解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3],[2,1,3], [1,3,4].
提示：
1 <= nums.length <= 2 * 1e4
1 <= nums[i], k <= nums.length
解析
-
如果寻找最多包含k个不同数字的连续子数组应该怎么做？
- 采用双指针的方法。
- 分别以数组内的每个数作为右指针，也就是子区间的结尾（连续区间的套路），计算出符合区间内数字种类小于等于k个的所有区间数。每个结尾对应的区间总数累加起来就是区间总数。
- 如果在右指针移动的过程中，区间数超过了k个，那么就要移动左指针，直至小于等于k个。
- 记录区间数种类可以使用数组，因为给定的数据范围不大。
-
恰好包含k个，可以转化为最多包含k个-最多包含k-1个，这样就得到恰好包含的k个的区间数。
-
滑动窗口的特点，
（1）区间需要满足固定的状态（种类数固定）
（2）区间状态随着右指针移动逐渐不符合，左指针移动可以重新回到这种状态（右动多，左动少，满足状态就计数）
（3）有一种随着像右移动单调的感觉（本题就是数字种类只会越来越多）
例如：1 2 1 3 4 ，k=2.
首先，最多包含两个，分别以1 2 1 3 4，作为区间的结尾。
1）1结尾，满足最多包含两个的区间数为1（1）
2）2结尾，满足最多包含两个的区间数为2（2 12）
3）1结尾，满足最多包含两个的区间数为3（1 12 121）
4）3结尾，满足最多包含两个的区间数为3（3 31 312）
5）4结尾，满足最多包含两个的区间数为3（4 43 431）
因此，最多包含2个不同数的区间为g(2)=1+2+3+3+3=12个
同理，最多包含一个数的区间为，g(1)=1+1+1+1+1=5个
因此，恰好为2个的区间数位 12 - 5 = 7
code
class Solution {
public:
int ok(vector<int>& nums,int k){
int n=nums.size();
// 区间内数字种类
int cnt=0;
// 记录区间内有哪些数字，以及数量
vector<int> vis(n+1,0);
int l=0,r=0;
int res=0;
while(r<n){
if(!vis[nums[r]])
cnt++;
vis[nums[r]]++;
// 不符合，左指针移动，直到符合状态
while(cnt>k){
vis[nums[l]]--;
if(!vis[nums[l++]])
cnt--;
}
// 以r结尾的子区间数
res+=r-l+1;
r++;
}
return res;
}
int subarraysWithKDistinct(vector<int>& nums, int k) {
return ok(nums,k)-ok(nums,k-1);
}
};
