K 个不同整数的子数组

K 个不同整数的子数组

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

考虑尺取.首先定义一个函数 ,表示 数组中有多少个子数组 ,满足 中不同数的个数小于等于 ,然后答案就是 .
算 时,定义一个 数组记录每个数出现的次数,当 这个区间不同数的个数大于 时,左指针 右移.每一次得到合法的区间 时,对答案的贡献为 .

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;
    }
};