LeetCode 第993题 Subarrays with K Different Integers【滑动窗口】（Java）
原题地址： https://leetcode.com/problems/subarrays-with-k-different-integers/
要求如下：
给定一个正整数的数组，寻找（连续，但是元素不一定不重复的）子数组，满足条件就是里面不同的数字的数量，正好是K个。
例如[1,2,3,1,2]有三个不同的数字，1，2，3。
要求返回这样的子数组的数量。
例 1:
输入: A = [1,2,1,2,3], K = 2
输出: 7
正好有两个数字的子数组包括 [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]，7个。
例 2:
输入:A = [1,2,1,3,4], K = 3
输出: 3
正好三个数字的子数组包括[1,2,1,3], [2,1,3], [1,3,4]。
注意:
1 <= A.length <= 20000
1 <= A[i] <= A.length
1 <= K <= A.length
前面几道题，我都是独立做出来的，但是992题，我看了leetcode的解题，还看了youtube的视频（见参考文献）。在我研究滑动窗口算法之前，这道题我还做过暴力解，应该是对的，但是速度有点慢，在leetcode上面提交的时候timeout了。
我学习了leetcode提供的解答和youtube视频的解法，但是我都自己实现了一遍。
这个题目的难度在于，一开始我一直想用一个滑动窗口解开，但是发现很难。后来，我看了 leetcode 的解法，其实要点就是用了两个窗口。
首先我们会发现包含的字符数正好等于K很难做，但是字符数小于等于K相当好做。首先left和right都为0，以例1为例。逐步移动right，这时候从0开始一直到3，包含的字符都是小于2的，然后移动left，直到字符数小于K，也就是只有一个字符，在这个过程中，每一个left和right的组合都是合法的。然后继续移动right到最后，然后一步步移动left直到字符数小于K。所以，这是一个常规的算法。
算法如下，字符数小于等于K：
如果，字符数小于等于K的函数 subarraysWithMostKDistinct 定义出来了。
那么subarraysWithMostKDistinct(k) – subarraysWithMostKDistinct(k-1)不就是正好等于K的结果么？
所以结果函数写为：
这个实际上是youtube上的解法。但是，我们在仔细一想，leetcode上面的解法，其实跟这个是一个意思。只不过，leetcode解法，把两次调用mostk改成了一个是mostk的left指针和一个mostk-1的指针而已。代码如下，这个题感觉很绕，但是想通了，代码并不复杂（我的看起来复杂是因为我特意写成跟leetcode不一样的形式来验证我是不是自己可以重新写得出来。leetcode的代码形式很简洁。）：
本题代码地址为: https://github.com/tinyfool/leetcode/tree/master/src/p0992
本文假设你对滑动窗口概念有所了解，如果你对滑动窗口的概念不够了解，请参看我介绍 滑动窗口的文章，里面有详细的解释 。
参考文献：
- 花花酱 LeetCode Weekly Contest 123 (989, 990, 991, 992) – 刷题找工作
正文到此结束
热门推荐
相关文章
近期评论
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
搞个gitee的项目
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
