【滑动窗口】个人练习-Leetcode-992. Subarrays with K Different Integers

题目链接：https://leetcode.cn/problems/subarrays-with-k-different-integers/description/

题目大意：给一个数组nums[]，求【不同元素刚好为k个】的子列的个数。子列要求连续。

思路：主要是转换题意，可以先求【不同元素最多为k个】的子列数，然后再求【不同元素最多为k-1个】的子列数，两者相减就是【不同元素刚好为k个】的子列数。思路有点像前缀和。

那么可以用滑动窗口来解决。对于每一个固定的右端点r，找一个左端点l（从最左边开始找）使得刚好[l, r]区间里的不同元素个数刚好为k（这样就是最多为k个的情况）。然后这个l可以作为下一轮的新起点，因为下一轮r往右移动了，使得不同元素数只会增加或者不变，l没必要再从0开始，只要从上一轮的l开始就行了。

每一轮中的r-l刚好就是【新增子列数】，因为新增子列是连续的，并且必然包含nums[r]，这些子列即为以r为右端点，长度为1, 2, ..., r-l的子列。

完整代码

class Solution {
public:int kDis(vector<int>& nums, int k) {int n = nums.size();vector<int> freq(n+1, 0);int l = 0, r = 0, res = 0;int disn = 0;while (r < n) {if (freq[nums[r]] == 0)disn++;freq[nums[r]]++;r++;while (disn > k) {freq[nums[l]]--;if (freq[nums[l]] == 0)disn--;l++;}res += r - l;}return res;}int subarraysWithKDistinct(vector<int>& nums, int k) {return kDis(nums, k) - kDis(nums, k-1);}
};