内容简介：原题地址：前面几道题，我都是独立做出来的，但是992题，我看了leetcode的解题，还看了youtube的视频（见参考文献）。在我研究滑动窗口算法之前，这道题我还做过暴力解，应该是对的，但是速度有点慢，在leetcode上面提交的时候timeout了。我学习了leetcode提供的解答和youtube视频的解法，但是我都自己实现了一遍。
原题地址： 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
本文假设你对滑动窗口概念有所了解，如果你对滑动窗口的概念不够了解，请参看我介绍 滑动窗口的文章，里面有详细的解释 。
参考文献：
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Foundation Web Standards
Jonathan Lane、Steve Smith / Friends of ED / 21st July 2008 / $34.99
Foundation Web Standards explores the process of constructing a web site from start to finish. There is more to the process than just knowing HTML! Designers and developers must follow a proper proces......一起来看看 《Foundation Web Standards》 这本书的介绍吧!
