Subarrays with K Different Integers

题目
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)解法

暴力解法是首先用一个循环遍历数组的每个元素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

那么你会发现
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

最后编辑于：2019.07.01 13:12:04