LeetCode 992 K 个不同整数的子数组

本题是一道滑动窗口的典型题目，需要灵活掌握算法知识，并能对题目的求解问题进行转化，以引入已知的问题求解思路。

题目描述

原题链接如下： LeetCode 992 K 个不同整数的子数组

题目大意

已知一个保存正整数的数组 A，其子数组（元素必须相邻）内部的元素种类自然各不相同，假设给出固定的数字 K，求元素种类为 K 的子数组的数目。

输入与输出

示例输入为：

1
2
3
4
5
6
7

Intput 1:
A = [1, 2, 1, 2, 3]
K = 2

Input 2:
A = [1, 2, 1, 3, 4]
K = 3

• A 的长度范围是 $[1, 20000]$
• A 内的元素大小不会超过他的长度
• K 不会超过 A 的长度

对应输出为：

1
2
3
4
5

Output 1:
7

Output 2:
3

解题思路

如果直接使用枚举法需要枚举有 n 个 元素的数组 A 的所有子数组，然后进行元素种类计数，需要先枚举 $n^{2}$ 个子数组，然后遍历子数组元素进行计数，可以大体估计时间复杂度为 $O(n^{3})$，效率低下，显然无法通过。当然，在求解子串、子数组等问题时，我们很容易联想到滑动窗口方法，但是本题却不能直接套用滑动窗口的模板代码。因为一般情况下如果要应用滑动窗口方法，要求滑动窗口扩大时内部目标数值有单调性。但是本题如果一个窗口的左侧固定，却可能有多个右侧边界对应同一个元素数量，如下图所示：

这样，窗口的左边界固定，右边界却无法确定，使得遍历工作复杂度上升。

其实，我们不妨回想一般使用滑动窗口处理的问题常常是“最值”问题（毕竟和单调性相关），那么我们不妨把问题转化为“求最多有 K 种元素的子数组的个数”，这个问题的滑动窗口目标值满足单调性，因为这个问题实际就是“求内部有 K 个不同种元素的子数组的最大长度”的变种。 仍拿上图举例：我们在固定左边界为 A 的最左侧的时候，如果要求对应的 2 种元素的子数组的最大长度为 4，其实是在第一次遇到元素 2 的时候扩张窗口，不断比较抛弃了较小的子数组，直到遇到最后一个元素 2，即得到目标子数组是 $[1, 2, 1, 2]$。这样，其实这个目标子数组内部的所有子数组都满足“最多有 2 种元素的子数组”，而他们的数量就是子数组的长度 4。而滑动窗口方法可能会遇到多个这样的目标子数组，只要不用比较操作求最值而使用累加操作计数，即可得到所有满足要求的子数组的个数。 最后，恰好有 K 个元素的子数组的个数就十分好求解了，只要减去最多有 K - 1 个元素的子数组的数目即可。相当于序列的通项公式不好求解，可是序列和通项公式易求解的问题。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
    fun subarraysWithKDistinct(A: IntArray, K: Int): Int {
        return atMostKDistinct(A, K) - atMostKDistinct(A, K - 1)
    }

    private fun atMostKDistinct(A: IntArray, K: Int): Int {
        var l = 0
        val bucket = IntArray(A.size + 1)
        var re = 0
        var count = 0
        var r = 0
        while (r < A.size) {
            if (bucket[A[r]] == 0) count++
            bucket[A[r]]++
            r++
            while (count > K) {
                bucket[A[l]]--
                if (bucket[A[l]] == 0) count--
                l++
            }
            re += r - l
        }
        return re
    }
}