題目
Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K.

(For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.)

Return the number of good subarrays of A.

Example 1:

Input: A = [1,2,1,2,3], K = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
Example 2:

Input: A = [1,2,1,3,4], K = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

*思路

這個題是思考過程可以從暴力O(n^2)解法evolve到三指針的O(n)解法

暴力解法是首先用一個循環(huán)遍歷數組的每個元素i
For every starting point i, try to find number of valid subarrays starting from i
例如[1,2,2], K = 2
i = 0時，我們可以得出的valid subarrays有[1,2]和[1,2,2]這2個
Do this for every i in array A, you'll get the answer

暴力解法的缺點是當正在遍歷元素 i 時，你每次都得用另一個指針j從i的位置開始遍歷后面的所有元素才能知道有哪些valid subarrays。所以時間復雜度是O(n^2)

可以看出每次遍歷一個新的元素i，指針j總是得回撤到i的位置然后開始遍歷后面的元素
雙指針的算法多數都是利用求解答案的某些特性，讓我們無需回撤指針從而達到降低一個級別的時間復雜度

例如[1,2,1,2,3], K = 2
i = 0時, valid subarrays有[1,2], [1,2,1], [1,2,1,2] (一共3個)
我們可以有一根指針left讓它指向從i開始第一個遇到的valid subarray的末端(用一個dict1 keep track of number of distinct numbers in A[i...left], 如果len(dict1)等于K，則找到了left的位置)

用一根right指針指向最后一個遇到的valid subarray的末端(用一個dict2 keep track of number of distinct numbers in A[i...right], 如果len(dict2)等于K，而且right如果再向右移動就會導致len(dict2) > K)
在我們的這個例子input里，left = 1, right = 3

那么你會發(fā)現
number of valid subarrays starting from i is just equal to right - left + 1 = 3 - 1 + 1 = 3
這3個valid subarrays分別是A[i...left], A[i...left+1], A[i...right]

i = 1時
也需要找到相對于i = 1的對應的left和right指針，就可以計算出number of valid subarrays starting from i
當i = 1時，我們就不用考慮A[0]。A[0...left]本來是valid的，但是A[1...left]就不一定valid了。
所以left指針要向右邊探，使得A[1...left]也變得valid。同理right指針要向右移動使得A[1...right]變得valid。
當重新計算出相對于i = 1的對應的left和right指針，我們又知道了number of valid subarrays starting from i = 1了

以此類推遍歷完i = 0,1,2...n就行了
期間涉及到3個指針(i, left, right)，由于他們全程都只需要向右移動，直到數組結尾，所以時間復雜度是O(n)

答案

class Solution(object):
    def subarraysWithKDistinct(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: int
        """
        # window[number] -> occurrences of number
        window1 = {}
        window2 = {}
        
        ans = 0
        left, right = 0, 0
        for i in range(len(A)):
            # Move left pointer to closet place s.t [i...left] has exactly K distinct chars
            # Move right pointer to as far as possible s.t [i...right] has exactly K distinct chars
            while left < len(A):
                if len(window1) == K:
                    break
                window1[A[left]] = window1.get(A[left], 0) + 1
                left += 1
            if len(window1) < K:
                continue
                
            while right < len(A):
                if len(window2) == K:
                    break
                window2[A[right]] = window2.get(A[right], 0) + 1
                right += 1

            while right < len(A):
                if A[right] not in window2:
                    break
                else:
                    window2[A[right]] = window2.get(A[right], 0) + 1
                    right += 1
            
            ans += (right - left + 1)

            window1[A[i]] -= 1
            if window1[A[i]] == 0:
                window1.pop(A[i])

            window2[A[i]] -= 1
            if window2[A[i]] == 0:
                window2.pop(A[i])
             
        return ans