内容简介：原题地址：前面几道题，我都是独立做出来的，但是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
本文假设你对滑动窗口概念有所了解，如果你对滑动窗口的概念不够了解，请参看我介绍 滑动窗口的文章，里面有详细的解释 。
参考文献：
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Learning JavaScript
Shelley Powers / Oreilly & Associates Inc / 2006-10-17 / $29.99
As web browsers have become more capable and standards compliant, JavaScript has grown in prominence. JavaScript lets designers add sparkle and life to web pages, while more complex JavaScript has led......一起来看看 《Learning JavaScript》 这本书的介绍吧!
