K 个不同整数的子数组。
给定一个正整数数组 A,如果 A 的某个子数组中不同整数的个数恰好为 K,则称 A 的这个连续、不一定不同的子数组为好子数组。
(例如,[1,2,3,1,2] 中有 3 个不同的整数:1,2,以及 3。)
返回 A 中好子数组的数目。
来自力扣992。
两个窗口的滑动窗口。k-1窗口,k窗口。
时间复杂度:O(N)。
空间复杂度:O(N)。
代码用golang编写。代码如下:
package main
import "fmt"
func main() {
arr := []int{1, 2, 1, 2, 3}
ret := subarraysWithKDistinct2(arr, 2)
fmt.Println(ret)
}
func subarraysWithKDistinct2(arr []int, k int) int {
return numsMostK(arr, k) - numsMostK(arr, k-1)
}
func numsMostK(arr []int, k int) int {
i := 0
res := 0
count := make(map[int]int)
for j := 0; j < len(arr); j++ {
if count[arr[j]] == 0 {
k--
}
count[arr[j]] = count[arr[j]] + 1
for k < 0 {
count[arr[i]] = count[arr[i]] - 1
if count[arr[i]] == 0 {
k++
}
i++
}
res += j - i + 1
}
return res
}
执行结果如下: