LeetCode 992. Subarrays with K Different Integers

很容易联想到 at most distinct k 等一连串sliding window的问题，但是真正做起来发现困难重重。

具体来说，通过sliding window我们的确可以得到一个个以a[i]结尾的，exactly k个不同元素的最长window。但是我们很难求出这样的window中一共有多少subarray。

换个思路，exactly(K) = atMost(K) - atMost(K-1)

而 atMost(K) 就无限接近 340. Longest Substring with At Most K Distinct Characters。

每次计算当前window里以a[i]结尾的subarray，即 i-start+1，这样绝对不会遗漏，因为每个元素都会被遍历到。

class Solution {
public:
    int subarraysWithKDistinct(vector<int>& A, int K) {
        return subarraysWithAtMostK(A,K)-subarraysWithAtMostK(A,K-1);
    }

    int subarraysWithAtMostK(vector<int> &A, int k){
        unordered_map<int,int> count;
        int start=0, res=0;
        for (int i=0;i<A.size();++i){
            ++count[A[i]];
            while (count.size()>k){
                if (--count[A[start]]==0)
                    count.erase(A[start]);
                ++start;
            }
            res += i-start+1;
        }
        return res;
    }
};

当然不单独写函数，在一个for循环里维护两个start做可以one pass。