Leetcode992-K个不同整数的子数组[两种方法] 关键词 滑窗

题目

1 <= nums.length <= 20000
1 <= nums[i], k <= nums.length

方法一：滑窗右端每次+1，左端来回滑动

这道题初步看上去像滑窗。滑窗解决的问题是“最长”，比如找“无重复字符的最长子串”、“特定排列的子串”。通用方法就是滑窗右侧尽可能向右，直到滑窗内元素的个数不满足要求那么滑窗左侧右移。

本题考虑的不是“最多K个不同整数”，而是“恰好K个不同整数”。

我的办法（方法一）是先用滑窗找到“最多K个不同整数”的每个左右边界，然后对于这其中的每一个右边界，左边界“尝试右移”，找到全部合适的左边界。比如序列12123，对于第二个2来说，“最多2个不同整数”，就是1212，满足条件的左边界有3个，[1]212、[2]12、[1]2.

具体到代码实现，对于每一个右边界（即将加入滑窗）的值来说：

1. 如果这个值曾经在滑窗中出现过，则把该值加入滑窗之后，滑窗内仍然是恰好K种数，那么pl“尝试右移”：cnt数组相应减少，直到遇到第一个将cnt的某个非零值减到0位置的位置tmp_pl,那么tmp-pl就是此时右边界对应所有左边界的个数。然后把pl~tmp_pl区间内的数再加回cnt数组（恢复）。
2. 如果这个值没有在滑窗中出现，那么把该值加入滑窗之后，滑窗内就有K+1种数了，此时pl必须右移。右移到合适位置后，再进行1中的“尝试右移”操作。

class Solution {int cnt[20010] = {0};int ans = 0;public:int subarraysWithKDistinct(vector<int>& nums, int k) {int pl = 0, pr = 0, k2 = 0;// 先找k个不同的，定下初始滑窗位置 左闭右开for (; pr < nums.size() && k2 < k; pr++)if (++cnt[nums[pr]] == 1) k2++;if (k2 < k) return 0;ans++;// 开始滑动while (pr < nums.size()) {// 先尝试pl右移int tmp_pl = pl;while (cnt[nums[tmp_pl]] > 1) {ans++;cnt[nums[tmp_pl]]--; tmp_pl++;}// 恢复while (tmp_pl > pl) {tmp_pl--;cnt[nums[tmp_pl]]++;}// if 下一个数是旧数，加入if (cnt[nums[pr]] > 0) {cnt[nums[pr]]++; pr++;ans++;}// if 下一个数是新数，pl右移至窗内种类数-1else {cnt[nums[pr]]++; pr++;do {cnt[nums[pl]]--;pl++;} while (cnt[nums[pl - 1]] > 0);ans++;}}// 尝试pl右移int tmp_pl = pl;while (cnt[nums[tmp_pl]] > 1) {ans++;cnt[nums[tmp_pl]]--;tmp_pl++;}return ans;}
};

时间复杂度：最坏是Onn，但是实际还不错。

方法二：（最多K种的子串数） - （最多K-1种的子串数） = 恰好K种

这个方法是官方题解法。

还是12123，且K=2这个例子，对于1212来说，有3个左边界可以满足“恰好K种”，这个3是怎么算出来的呢？最多K-1种的左边界是1个，一共4个潜在的左边界，4-1=3.

（最多K种的子串数） - （最多K-1种的子串数） = 恰好K种

时间复杂度On