目录

一、题目内容

二、解题思路

三、代码

一、题目内容

给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。

（例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）

返回 A 中好子数组的数目。

示例 1：

输入：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].

示例 2：

输入：A = [1,2,1,3,4], K = 3
输出：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

二、解题思路

最多存在 K 个不同整数的子区间的个数与恰好存在K个不同整数的子区间的个数的差恰好等于最多存在 K - 1个不同整数的子区间的个数。

因此，最多存在 K 个不同整数的子区间的个数 - 最多存在 K - 1个不同整数的子区间的个数 = 恰好存在K个不同整数的子区间的个数。

三、代码

  

   

    

     

    
    

     

      class Solution:
     
    
   

    

     

    
    

     
 def subarraysWithKDistinct(self, A: list, K: int) -> int:
     
    
   

    

     

    
    

     
 return self._subarrayWithDistinct(A, K) - self._subarrayWithDistinct(A, K - 1)
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 # 计算最多为K的子数组长度
     
    
   

    

     

    
    

     
 def _subarrayWithDistinct(self, A, K):
     
    
   

    

     

    
    

     

       freq_num = [0 for _ in range(len(A) + 1)]
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       left, right = 0, 0
     
    
   

    

     

    
    

     

       count = 0
     
    
   

    

     

    
    

     

       res = 0
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 while right < len(A):
     
    
   

    

     

    
    

     
 if freq_num[A[right]] == 0:
     
    
   

    

     

    
    

     

       count += 1
     
    
   

    

     

    
    

     

       freq_num[A[right]] += 1
     
    
   

    

     

    
    

     

       right += 1
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 while count > K:
     
    
   

    

     

    
    

     

       freq_num[A[left]] -= 1
     
    
   

    

     

    
    

     
 if freq_num[A[left]] == 0:
     
    
   

    

     

    
    

     

       count -= 1
     
    
   

    

     

    
    

     

       left += 1
     
    
   

    

     

    
    

     
 # 长度贡献
     
    
   

    

     

    
    

     

       res += right - left
     
    
   

    

     

    
    

     
 return res
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      if __name__ == '__main__':
     
    
   

    

     

    
    

     

       s = Solution()
     
    
   

    

     

    
    

     

       A = [1, 2, 1, 2, 3]
     
    
   

    

     

    
    

     

       K = 2
     
    
   

    

     

    
    

     

       ans = s.subarraysWithKDistinct(A, K)
     
    
   

    

     

    
    

     

       print(ans)
     
    
  
 

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/113766832