2022-01-13：K 个不同整数的子数组。 给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定不同的子数组为好子数组。 （例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。） 返回 A 中好子数组的数目。 来自力扣992。

答案2022-01-13：

两个窗口的滑动窗口。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
}

执行结果如下： 图片

左神java代码