992. Subarrays with K Different Integers

Loading...LeetCode

sliding window，移动左指针的条件比较复杂，两种情况下移动左指针：

一、最左元素计数超过1：说明当前窗口一定有某些子数组也满足条件，移动左指针去逼进这些子数组，加入结果（所以这里会有local result）。

二、窗口内元素超过K种：移动左指针，使元素回到2种。

两种情况都是移动到再次符合条件为止。

class Solution:
    def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
        freq = defaultdict(int)
        res = 0
        count = 0
        
        l, r = 0, 0
        local = 1
        
        while r < len(A):
            
            freq[A[r]] += 1
            if freq[A[r]] == 1: count += 1
                
            while count > K or freq[A[l]] > 1:
                if count > K: 
                    print("count > K:", A[l:r])
                    local = 1
                    count -= 1
                else:
                    local += 1
                    
                freq[A[l]] -= 1
                l += 1
            
            if count == K:
                res += local
                
            r += 1

        return res