LeetCode 第992题 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

本文假设你对滑动窗口概念有所了解,如果你对滑动窗口的概念不够了解,请参看我介绍滑动窗口的文章,里面有详细的解释

参考文献:

打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据