992. K 个不同整数的子数组
992. K 个不同整数的子数组
难度困难
给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。
（例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）
返回 A 中好子数组的数目。
示例 1：
输入：A = [1,2,1,2,3], K = 2
输出：7
解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].示例 2：
输入：A = [1,2,1,3,4], K = 3
输出：3
解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].提示：
1 <= A.length <= 200001 <= A[i] <= A.length1 <= K <= A.length
函数签名：
func subarraysWithKDistinct(A []int, K int) int分析
朴素解法是 O(n^2) 的复杂度，会超时。直觉可以用滑动窗口来优化。
不过，当窗口一端固定，满足窗口内恰好有 K 个不同数字的窗口会有多个，如示例1，假设固定窗口左端点在索引 0，那么右端点可以是 1、2 或 3 。
如果窗口元素满足的条件改变，变成窗口内**“最多”有 K 个不同数字就好了。窗口左端点固定，右端点也就是唯一确定的。也就是滑动窗口能解决“最多”、“最少”的问题，但是不能解决“恰好”**的问题。
两个滑动窗口
好在这个问题可以转化。**“恰好”的区间可以由两个“最多”***的区间确定：
|<--------------最多k个----------------->|
|<---最多k-1个---->|<------恰好k个------->|或者
|<--------------最多k个----------------->|
|<---恰好k个---->|<-----最多k-1个-------->|这样可以用两个滑动窗口，分别维护窗口中**“最多”有 K 个不同数字和“最多”**有 K-1 个不同数字。为了编码方便，可以维持这两个窗口的右端点相同，左端点不同，即上边第二个图示。
具体算法：
每次两个窗口的右端点向右移动一步，窗口添加右端点所指的数字，根据窗口内所有数字分别更新两个窗口的左端点 i 和 j 指针。
如果两个窗口中的元素个数正好满足设定，那么结果就要加上 |i-j|，即对于到当前右端点，会有|i-j|个左端点和其形成的窗口里恰好有 K 个不同数字。
func subarraysWithKDistinct(A []int, K int) int {
n := len(A)
if n < K {
return 0
}
res := 0
// memo1、memo2 分别记录两个窗口里不同数字的个数
memo1 := make(map[int]int, n)
memo2 := make(map[int]int, n)
// i、j分别为两个窗口的左端点
i, j := 0, 0
for _, v := range A {
memo1[v]++
memo2[v]++
for len(memo1) > K {
memo1[A[i]]--
if memo1[A[i]] == 0 {
delete(memo1, A[i])
}
i++
}
for len(memo2) > K-1 {
memo2[A[j]]--
if memo2[A[j]] == 0 {
delete(memo2, A[j])
}
j++
}
if len(memo1) == K && len(memo2) == K-1 {
res += j - i
}
}
return res
}时空复杂度都是 O(n)。
两遍滑动窗口
可以把这个问题抽象得更到位些：可以用两次常规的滑动窗口解法，分别计算出最多有 K 个不同数字的子数组个数和最多有 K-1 个不同数字的子数组的个数；这两个结果相减就是这个问题的答案。
如果要计算满足题意的最长子串的长度会比较简单，这里是计算满足题意的子串的个数，结合下边 atMostKDistinct 函数的注释，需要想一想这个问题。
func subarraysWithKDistinct(A []int, K int) int {
if len(A) < K {
return 0
}
return atMostKDistinct(A, K) - atMostKDistinct(A, K-1)
}
// 计算 nums 中最多包含 k 个不同数字的子数组的个数
func atMostKDistinct(nums []int, k int) int {
res := 0
left := 0
memo := make(map[int]int, len(nums))
for right, v := range nums {
memo[v]++
for len(memo) > k {
memo[nums[left]]--
if memo[nums[left]] == 0 {
delete(memo, nums[left])
}
left++
}
// [left, right] 区间的长度就是对结果的贡献
// 整个过程相当于枚举窗口右端点，在右端点固定的情况下确定左端点
// 因为窗口元素满足限定，所以对于一个确定的右端点 right，有 right-left+1 个子窗口满足限定
res += right - left + 1
}
return res
}时空复杂度都是 O(n)。