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

文章目录

题目
方法一：滑窗右端每次+1，左端来回滑动
方法二：（最多K种的子串数） - （最多K-1种的子串数） = 恰好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.

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

如果这个值曾经在滑窗中出现过，则把该值加入滑窗之后，滑窗内仍然是恰好K种数，那么pl“尝试右移”：cnt数组相应减少，直到遇到第一个将cnt的某个非零值减到0位置的位置tmp_pl,那么tmp-pl就是此时右边界对应所有左边界的个数。然后把pl~tmp_pl区间内的数再加回cnt数组（恢复）。
如果这个值没有在滑窗中出现，那么把该值加入滑窗之后，滑窗内就有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右移至窗内种类数-1
            else {
                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;
    }
};