992.md

992 Subarrays with K Different Integers

Description

link

---

Solution

• 右边保持滑动，左边保存两个变量l，r分别代表从l，r到右边区间内存在K个以及K-1个不同整数的区间
• 此时答案即为加上r-l即可

---

Code

O(n) O(n)

class Solution:
    def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
        def Most(A, K):
            cnt = collections.Counter()
            res = 0
            l = 0
            for r in range(len(A)):
                cnt[A[r]] += 1
                while len(cnt) > K:
                    cnt[A[l]] -= 1
                    if cnt[A[l]] == 0:
                        del cnt[A[l]]
                    l += 1
                res += r - l + 1
            return res
        return Most(A, K) - Most(A, K - 1)