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

题目大意 #

这道题考察的是滑动窗口的问题。

给出一个数组 和 K，K 代表窗口能能包含的不同数字的个数。K = 2 代表窗口内只能有 2 个不同的数字。求数组中满足条件 K 的窗口个数。

解题思路 #

如果只是单纯的滑动窗口去做，会错过一些解。比如在例子 1 中，滑动窗口可以得到 [1,2], [1,2,1], [1,2,1,2], [2,1,2], [1,2], [2,3], 会少 [2,1] 这个解，原因是右边窗口滑动到最右边了，左边窗口在缩小的过程中，右边窗口不会再跟着动了。有同学可能会说，每次左边窗口移动的时候，右边窗口都再次从左边窗口的位置开始重新滑动。这样做确实可以，但是这样做完会发现超时。因为中间包含大量的重复计算。

这道题就需要第 3 个指针。原有滑动窗口的 2 个指针，右窗口保留这个窗口里面最长的子数组，正好有 K 个元素，左窗口右移的逻辑不变。再多用一个指针用来标识正好有 K - 1 个元素的位置。那么正好有 K 个不同元素的解就等于 ans = atMostK(A, K) - atMostK(A, K - 1)。最多有 K 个元素减去最多有 K - 1 个元素得到的窗口中正好有 K 个元素的解。

以例子 1 为例，先求最多有 K 个元素的窗口个数。

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

每当窗口滑动到把 K 消耗为 0 的时候，res = right - left + 1 。为什么要这么计算，right - left + 1 代表的含义是，终点为 right，至多为 K 个元素的窗口有多少个。[left,right], [left + 1,right], [left + 2,right] …… [right,right]。这样算出来的解是包含这道题最终求得的解的，还多出了一部分解。多出来的部分减掉即可，即减掉最多为 K - 1 个元素的解。

最多为 K - 1 个元素的解如下：

[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
}