【leetcode-Python】-滑动窗口-992. Subarrays with K Different Integers

65 阅读 0 评论 43 点赞

我是靠谱客的博主可耐往事，最近开发中收集的这篇文章主要介绍【leetcode-Python】-滑动窗口-992. Subarrays with K Different Integers，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接

https://leetcode.com/problems/subarrays-with-k-different-integers/

题目描述

给定一个元素均为正整数的数组A，如果A的某个子数组（元素索引连续，且可以有重复元素）中不同整数的个数恰好为K，则称A的这个子数组为好子数组。返回A中好子数组的数目。（从示例中可以看出，内容相同但起始终止索引不同的子数组被认为是不同的子数组）

示例

输入：A=[1,2,1,2,3],K=2

输出：7

恰好由2个不同整数组成的子数组： [1,2],[2,1],[1,2],[2,3],[1,2,1],[2,1,2],[1,2,1,2]

解题思路

滑动窗口算法可以将嵌套的循环问题转化为单循环问题，从而降低时间复杂度。在滑动窗口算法中，要根据条件固定左右指针中的某一个，然后移动另外一个。比如在【leetcode-Python】-滑动窗口-76. Minimum Window Substring（最小覆盖子串）返回s中涵盖t中所有字符的最小子串问题中，首先右指针右移，直到窗口内元素能够包含t中所有字符，左指针右移缩小窗口试图找到更小的子串，直到窗口内不能覆盖t，再次右移右指针。

常规滑动窗口算法适用的题目条件：

（1）求子串问题，窗口内元素连续。

（2）窗口只能从左向右滑动，不能逆过来滑动。即窗口的左右边界只能从左向右增加，不能减少（具有单调性）。

但是对于这道题“恰好有k个不同整数”，不能用常规的滑动窗口算法求解。因为固定左边界后，会发现能够满足条件的右边界可能有多个。

比如A=[1,2,1,2,3]，k=2，最开始左边界固定为0，移动右边界。会发现包含2个不同整数的子数组有3个：[1,2],[1,2,1],[1,2,1,2]。那么右边界移动到哪里，左边界才可以移动呢？

（1）如果发现一个满足条件的子数组就开始移动，即找到[1,2]后，就固定右指针，移动左指针，那么就会漏掉[1,2,1]和[1,2,1,2]这两个同样以A[0]开头的子数组。

（2）如果右指针一直移动，直到以left开头的子数组不满足条件后停下来，即找全[1,2],[1,2,1],[1,2,1,2]后再停下来并移动左指针，此时right指向元素3，由于right不能左移，会漏掉[2,1],[2,1,2]这些子数组。

因此我们可以将问题进行转换：将“恰好”改为“最多”。为什么可以这样修改呢？

（1）求A中某个子数组不同整数个数最多为K时，我们可以用常规滑动窗口算法来求解。因为固定左边界时，包含最多k种不同整数的子数组右边界是确定的。并且移动左边界时，右边界没有左移的需要。比如在A=[1,2,1*,2*,3]中找包含最多2种不同整数的子数组时，固定left指针在索引0的位置，右指针一直右移。（用1*，2*表示第二次出现的元素1和元素2）。right每新增1，新增找到的满足条件的数组个数为right-left。可以理解为新增的是以A[right-1]为末尾的子数组，那么新增的这部分子数组的个数就是right-left。

窗口内元素为[1]时，找到满足条件的子数组[1]（个数为1）；

窗口内元素为[1,2]时，新增满足条件的子数组[2],[1,2]（个数为2）。

窗口内元素为[1,2,1*]时，新增满足条件的子数组[1*],[2,1*],[1,2,1*]（个数为3）。

窗口内元素为[1,2,1*,2*]时，新增满足条件的子数组[2*],[1*,2*],[2,1*,2*],[1,2,1*,2*]（个数为4）。

左边界移动的条件为窗口内不同整数个数超过了K。窗口内元素为[1,2,1*,2*,3]时，满足左边界移动条件。右指针固定，左指针右移。

left右移到索引1，窗口内元素为[2,1*,2*,3]，仍需要继续移动。

left右移到索引2，窗口内元素为[1*,2*,3]，仍需要继续移动。

left右移到索引3，窗口内元素为[2*,3],左边界固定。可以计算新增满足条件的子数组[3],[2*,3]（个数为2）。此时右边界也达到了数组末尾，因此循环结束。

（2）包含恰好K个不同整数子数组的个数可以由包含最多K个不同整数子数组个数和包含最多K-1个不同整数子数组个数推算出来：

最多包含k个不同整数的子数组个数=包含1个不同整数的子数组个数+包含2个不同整数的子数组个数+...+包含k个不同整数的子数组个数。

最多包含k-1个不同整数的子数组个数=包含1个不同整数的子数组个数+包含2个不同整数的子数组个数+...+包含k-1个不同整数的子数组个数。

因此有恰好包含k个不同整数的子数组个数 = 最多包含k个不同整数的子数组个数 - 最多包含k-1个不同整数的子数组个数。

Python实现

用distinct存储此时window中不同整数的个数，类似【leetcode-Python】-滑动窗口-76. Minimum Window Substring（最小覆盖子串）中的valid。

class Solution:
    def mostKDistinct(self,A,K):
        left,right = 0,0
        from collections import defaultdict
        window = defaultdict(int) #存储窗口内元素
        #用distinct存储window中不同整数的个数
        distinct = 0
        res = 0
        while(right<len(A)):
            c = A[right]
            right += 1
            if window[c] == 0:
                distinct += 1    
            window[c] += 1 #更新窗口内元素
            #左边界移动条件
            while(distinct>K): #窗口内元素不满足条件了，此时左边界右移
                d = A[left]
                left += 1
                window[d] -= 1
                if window[d] == 0:
                    distinct -= 1
            res += right - left #更新结果
        return res
    def subarraysWithKDistinct(self, A: List[int], K: int) -> int:         
        return self.mostKDistinct(A,K)-self.mostKDistinct(A,K-1)