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

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

参考文献:

打赏

5 thoughts to “LeetCode 第992题 Subarrays with K Different Integers【滑动窗口】(Java)”

  1. 您好,想請教一下,為什麼最後要做subarraysWithMostKDistinct(k) – subarraysWithMostKDistinct(k-1)?
    我一直想不透這樣做是什麼意思? 能否請你詳細解釋,萬分感謝。

    1. 这道题目的难点在于很难找到有正好K个不同数字的数组的代码。而subarraysWithMostKDistinct是说,有K个以及以下个不同数字的数组的代码,也就是说有1个数字的,2个数字的,……一直到K个。这个函数我们比较好写。我们会发现subarraysWithMostKDistinct(k-1)和subarraysWithMostKDistinct(k)有大量的重复,从1,2一直到k-1部分,都是重复的,不同的是k的部分。所以相减就得到了k的结果。

      你如果还不能理解,那你可以把subarraysWithMostKDistinct中间的结果数组,输出出来,比较一下subarraysWithMostKDistinct(k-1)和subarraysWithMostKDistinct(k)的输出,应该会比较好理解了。

  2. 很謝謝你的回覆。
    若以Input: A = [1,2,1,3,4], K = 3題目來看,程式碼如leetcode解答來看,每次經歷的數組如下,但subarraysWithMostKDistinct(k)和subarraysWithMostKDistinct(k-1)重複的部分只有前3個數組,後面2個數組都不一樣,我知道這邊是以總長度相減來得到答案,但以觀念來看我想不透為什麼答案會是3,請問我有哪邊想錯嗎? 謝謝。

    int atMostK(vector& A, int K)
    {
    int i = 0, res = 0;
    unordered_map count;
    for (int j = 0; j < A.size(); ++j)
    {
    if (!count[A[j]]++) K–;
    while (K < 0)
    {
    if (!–count[A[i]]) K++;
    i++;
    }
    res += j – i + 1;
    }
    return res;
    }

    subarraysWithMostKDistinct(k)
    1
    12
    121
    1213
    134

    subarraysWithMostKDistinct(k-1)
    1
    12
    121
    13
    34

    1. 按照Input: A = [1,2,1,3,4], K = 3題目來看,k-1=2.
      那么,subarraysWithMostKDistinct(3)包括(这叫最多3个,1个2个也都合法)
      1
      2
      3
      4
      12
      21
      121
      13
      34
      1213
      213
      134
      那么,subarraysWithMostKDistinct(2)包括(这叫最多2个,1个也合法)
      1
      2
      3
      4
      12
      21
      121
      13
      34
      差异不正好是3么?

  3. 您好,但我的code在跑subarraysWithMostKDistinct(3)並不會有下面這些子數組,請問是哪邊有漏掉?
    謝謝。

    2
    3
    4
    21
    13
    34
    213

发表评论

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

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