992. Subarrays with K Different Integers #
Problem #
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
Problem Meaning #
This problem tests the sliding window technique.
Given an array and K, K represents the number of distinct numbers that the window can contain. K = 2 means the window can only have 2 distinct numbers. Find the number of windows in the array that satisfy the condition K.
Solution Approach #
If you simply use a sliding window, you will miss some solutions. For example, in Example 1, the sliding window can get [1,2], [1,2,1], [1,2,1,2], [2,1,2], [1,2], [2,3], but it will miss the solution [2,1]. The reason is that the right side of the window has slid to the far right, and while the left side of the window is shrinking, the right side will not move along with it anymore. Some students may say that every time the left side of the window moves, let the right side of the window start sliding again from the position of the left side. This can indeed work, but after doing so you will find it times out. Because it contains a large amount of repeated computation.
This problem requires a 3rd pointer. For the original 2 pointers of the sliding window, the right window keeps the longest subarray in this window, which has exactly K elements, while the logic for moving the left window to the right remains unchanged. Use one more pointer to mark the position where there are exactly K - 1 elements. Then the solution with exactly K distinct elements is equal to ans = atMostK(A, K) - atMostK(A, K - 1). The number of windows with exactly K elements is obtained by subtracting the number of windows with at most K - 1 elements from the number of windows with at most K elements.
Using Example 1 as an example, first find the number of windows with at most K elements.
[1]
[1,2], [2]
[1,2,1], [2,1], [1]
[1,2,1,2], [2,1,2], [1,2], [2]
[2,3], [3]
Whenever the window slides until K is consumed to 0, res = right - left + 1. Why calculate it this way? The meaning of right - left + 1 is: with right as the endpoint, how many windows have at most K elements. [left,right], [left + 1,right], [left + 2,right] …… [right,right]. The solutions calculated this way include the final solutions required by this problem, but also contain some extra solutions. Just subtract the extra part, that is, subtract the solutions with at most K - 1 elements.
The solutions with at most K - 1 elements are as follows:
[1]
[2]
[1]
[2]
[3]
After subtracting the two, the result obtained is the final result:
[1,2]
[1,2,1], [2,1]
[1,2,1,2], [2,1,2], [1,2]
[2,3]
Code #
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
}
中文