每日算法系列【LeetCode992】K个不同整数的子数组

题目描述

给定一个正整数数组 A&＃xff0c;如果 A 的某个子数组中不同整数的个数恰好为 K&＃xff0c;则称 A 的这个连续、不一定独立的子数组为好子数组。 &＃xff08;例如&＃xff0c;[1,2,3,1,2] 中有 3 个不同的整数&＃xff1a;1&＃xff0c;2&＃xff0c;以及 3。&＃xff09;

返回 A 中好子数组的数目。

示例1

示例2

提示

• 1 <&＃61; A.length <&＃61; 20000
• 1 <&＃61; A[i] <&＃61; A.length
• 1 <&＃61; K <&＃61; A.length

题解

这题最暴力的方法就是用一个字典维护每个数出现的次数&＃xff0c;然后遍历所有的区间&＃xff0c;求出不同整数个数正好等于 K 的区间个数。 但是这种方法时间复杂度是 &＃xff0c;一定会超时&＃xff0c;所以考虑其他方法。

现在考虑右边界为 j 的情况&＃xff0c;左边界 i 有什么规律呢&＃xff1f; 我们可以证明&＃xff0c;满足 [i, j] 正好包含 K 个不同整数的 i 的取值是一段连续的区间。 假设 [i, j]包含 K 个不同整数&＃xff0c;同时 [i&＃39;, j] 也包含 K 个不同整数&＃xff08;i

有了这个性质之后&＃xff0c;对于任意的 j &＃xff0c;我们只需要求出左边界 i 的取值范围就行了。同样这里还是不能暴力求&＃xff0c;不然就和一开始没区别了嘛。 既然这样&＃xff0c;想想如果 j 的左边界 i 的范围得到了&＃xff0c;这时候我们继续求 j &＃43; 1 的左边界范围&＃xff0c;能不能利用一下之前得到的结果&＃xff1f;而不用重新计算。 很容易发现&＃xff0c;如果 j 右移了&＃xff0c; i 的取值范围也会右移&＃xff0c;因为 j 右移有两种结果&＃xff1a;一是引入了新的数&＃xff0c;二是某个存在的数的数量加 1 。 第一种情况对左边界没有任何影响&＃xff0c;因为不同整数数量没有变化&＃xff0c;还是 K 。第二种情况不同整数数量变成 K &＃43; 1 了&＃xff0c;这时候左边界一定要右移&＃xff0c;删掉点数&＃xff0c;才可能使区间符合题意。

有了上述的性质之后就好做了&＃xff0c;因为左边界的取值范围也是不断右移的&＃xff0c;所以我们只需要维护两个指针 l 和 r 就行了&＃xff0c;一个保存取值范围的最小值&＃xff0c;一个保存最大值。然后每次对于一个 j &＃xff0c;符合题意的子区间数量就是 r - l &＃43; 1 。而 j 右移一个数之后&＃xff0c; l 需要右移&＃xff0c;直到 [l, j] 中正好有 K 个不同整数&＃xff0c; r 也继续右移&＃xff0c;直到[r &＃43; 1, j] 中正好有 K - 1 个不同整数。

因为 l 和 r 最多只会移动 n 次&＃xff0c;而 j 也只移动了 n 次&＃xff0c;所以总体时间复杂度降到了 。

代码

c&＃43;&＃43;

python

后记

其实这题想起来可能好想&＃xff0c;但是写起来容易写错&＃xff0c;因为区间范围需要好好琢磨。这一类问题统称为“窗口滑动”问题&＃xff0c;都是不特别难&＃xff0c;想清楚了两个状态之间窗口如何滑动就行了。