困难题，先想着DP扫描，但是会爆栈；

 

主体思想仍然采用滑动窗口来进行；

但是对于该题目，有一个比较新的点，要利用脑经急转弯思想把问题转换一下；

 

对于正好为K个不同元素组成的最长字符串可以转换为：

最多由K个不同元素组成的字符串-最多由K-1个不同元素组成的字符串；

（这样可以有效的降低复杂度，使得单次区间寻找即可找到符合要求的字符串）

 

 

可以想象出，我们只需要寻找K个不同元素组成的字符串即可；

 

但是针对于该问题，统计字符串个数也有一个小tip；

当我们确定一个字符串为K个不同元素组成的字符串，那么他的子串也必定是对多由K个不同元素的组成的字符串；

 

因此，每次right和left确定区间，首先要找到当前的最长K个不同元素组成的字符串，然后统计子数组个数，即为right-left+1；

例如：1，2，1，2，4；

对于,1,2,1,2序列，可以有4个子序列：

1，2，1，2

2，1，2

1，2

2

所以可见，正好为k个整数的序列和最多为k个整数的序列都包含在内；

 

当遇到大于k的序列，立刻调整left指针，重新选找下一个符合条件的序列；

 

对于序列内不同元素计数，采用map计数即可；

 

class Solution {
public:
    int fun(vector<int>& A, int K) {
        map<int, int>mp;
        int len = A.size();
        int le = 0, ri = 0;
        int res = 0;
        int dis = 0;
        while (ri < len) {
            if (mp[A[ri]] == 0)
                dis++;
            mp[A[ri]]++;
            while (dis > K) {
                mp[A[le]]--;
                if (mp[A[le]] == 0) {
                    dis--;
                }
                le++;
            }
            res += ri - le + 1;
            ri++;
        }
        return res;
    }

    int subarraysWithKDistinct(vector<int>& A, int K) {
        return fun(A,K)-fun(A,K-1);
    }
};