Skip to content

Latest commit

 

History

History
142 lines (83 loc) · 3.51 KB

0992._Subarrays_with_K_Different_Integers.md

File metadata and controls

142 lines (83 loc) · 3.51 KB

992. Subarrays with K Different Integers

难度: Hard

刷题内容

原题连接

内容描述

Given an array A of positive integers, call a (contiguous, not necessarily distinct) subarray of A good if the number of different integers in that subarray is exactly K.

(For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.)

Return the number of good subarrays of A.

 

Example 1:

Input: A = [1,2,1,2,3], K = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
Example 2:

Input: A = [1,2,1,3,4], K = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].
 

Note:

1 <= A.length <= 20000
1 <= A[i] <= A.length
1 <= K <= A.length

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

For an index i, we define two pointers, left and right. 
left is defined as the smallest index such that A[left...i] has K distinct elements, 
right is defined as the largest index such that A[right...i] has K distinct element. 
Therefore, the number of subarrays ending at i that have K distinct elements is right-left+1. 
Each index enters any of the maps at most once, and exits at at most once. Therefore the complexity is O(N).

参考C++, O(N) algorithm, two maps for two pointers, easy to understand

class Solution:
    def subarraysWithKDistinct(self, A: 'List[int]', K: 'int') -> 'int':
        mapl, mapr = collections.defaultdict(int), collections.defaultdict(int)
        l, r, res = 0, 0, 0
        for i in range(len(A)):
            mapl[A[i]] += 1
            mapr[A[i]] += 1
            if len(mapr) < K:
                continue
            while len(mapl) > K:
                mapl[A[l]] -= 1
                if mapl[A[l]] == 0:
                    del mapl[A[l]]
                l += 1
            while len(mapr) > K:
                mapr[A[r]] -= 1
                if mapr[A[r]] == 0:
                    del mapr[A[r]]
                r += 1
            while mapr[A[r]] > 1:
                mapr[A[r]] -= 1
                r += 1
            res += r - l + 1
        return res

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(N)******

用寒神的思路+[第340题]的套路(只需要将res = max(res, r - l) 这行代码改成res += r - l即可)

class Solution:
    def subarraysWithKDistinct(self, A: 'List[int]', K: 'int') -> 'int':
        return self.subarraysWithAtMostKDistinct(A, K) - self.subarraysWithAtMostKDistinct(A, K-1)
    
    def subarraysWithAtMostKDistinct(self, s, k):
        lookup = collections.defaultdict(int)
        l, r, counter, res = 0, 0, 0, 0
        while r < len(s):
            lookup[s[r]] += 1
            if lookup[s[r]] == 1:
                counter += 1
            r += 1   # end 永远指向下一个待处理的字符
            while l < r and counter > k:
                lookup[s[l]] -= 1
                if lookup[s[l]] == 0:
                    counter -= 1
                l += 1
            res += r - l # 因此这里是r-l而不是r-l+1
        return res