0992. Subarrays With K Different Integers

# 992. 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].

``````

Note:

• 1 <= A.length <= 20000
• 1 <= A[i] <= A.length
• 1 <= K <= A.length

## 解题思路 #

``````[1]
[1,2], [2]
[1,2,1], [2,1], [1]
[1,2,1,2], [2,1,2], [1,2], [2]
[2,3], [3]
``````

``````[1]
[2]
[1]
[2]
[3]
``````

``````[1,2]
[1,2,1], [2,1]
[1,2,1,2], [2,1,2], [1,2]
[2,3]
``````

## 代码 #

``````
package leetcode

func subarraysWithKDistinct(A []int, K int) int {
return subarraysWithKDistinctSlideWindow(A, K) - subarraysWithKDistinctSlideWindow(A, K-1)
}

func subarraysWithKDistinctSlideWindow(A []int, K int) int {
left, right, counter, res, freq := 0, 0, K, 0, map[int]int{}
for right = 0; right < len(A); right++ {
if freq[A[right]] == 0 {
counter--
}
freq[A[right]]++
for counter < 0 {
freq[A[left]]--
if freq[A[left]] == 0 {
counter++
}
left++
}
res += right - left + 1
}
return res
}

``````

Sep 6, 2020