K 个不同整数的子数组

$Description$
给定一个数组 $A$ ,如果 $A$ 中的子数组不同数的个数为 $K$ ,则称为一个好数组,统计 $A$ 中有多少个好数组.

$Solution$
考虑尺取.首先定义一个函数 $f(A,K)$ ,表示 $A$ 数组中有多少个子数组 $a$ ,满足 $a$ 中不同数的个数小于等于 $K$ ,然后答案就是 $f(A,K)-f(A,K-1)$ .
算 $f(A,K)$ 时,定义一个 $dp$ 数组记录每个数出现的次数,当 $[l,r]$ 这个区间不同数的个数大于 $K$ 时,左指针 $l$ 右移.每一次得到合法的区间 $[l,r]$ 时,对答案的贡献为 $r-l+1$ .

$Code$

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& A, int K) {
        return f(A,K)-f(A,K-1);
    }
    int f(vector<int>&a,int K){
        int n=a.size();
        int dp[20005]={0};
        int l=0,r=0,ans=0,dis=0;
        while(r<n){
            dp[a[r]]++;
            if(dp[a[r]]==1)dis++;
            while(dis>K){
                dp[a[l]]--;
                if(!dp[a[l]])dis--;
                l++;
            }
            ans+=r-l+1;r++;
        }return ans;
    }
};