[Swift]LeetCode992.K个不同整数的子数组|SubarrayswithKDifferentIntegers

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10361564.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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 3different integers: 1, 2, and 3.)

Return the number of good subarrays of A.

Example 1:

Input: A = 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 = 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

给定一个正整数数组 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

Runtime: 432 ms

Memory Usage: 11.3 MB

 1 class Solution {
 2     func subarraysWithKDistinct(_ A: [Int], _ K: Int) -> Int {
 3         return count(A, K) - count(A, K-1)
 4     }
 5     
 6     func count(_ a:[Int],_ K:Int) ->Int
 7     {
 8         var n:Int = a.count
 9         var f:[Int] = [Int](repeating:0,count:n + 1)
10         var dis:Int = 0
11         var p:Int = 0
12         var ret:Int = 0
13         for i in 0..<n
14         {
15             f[a[i]] += 1
16             if f[a[i]] == 1
17             {
18                 dis += 1
19             }
20             while(dis > K)
21             {
22                 f[a[p]] -= 1
23                 if f[a[p]] == 0
24                 {
25                     dis -= 1
26                 }
27                 p += 1
28             }
29             ret += i-p+1
30         }
31         return ret
32     }
33 }

704ms

 1 class Solution {
 2     func subarraysWithKDistinct(_ A: [Int], _ K: Int) -> Int {
 3         var count = 0
 4         
 5         var dict1: [Int: Int] = [:]
 6         var dict2: [Int: Int] = [:]
 7 
 8         var l1 = 0
 9         var l2 = 0
10         
11         var r = 0
12         
13         while r < A.count {
14             let num = A[r]
15             
16             dict1[num, default: 0] += 1
17             dict2[num, default: 0] += 1
18 
19             while dict1.keys.count > K {
20                 let l1Num = A[l1]
21                 dict1[l1Num]! -= 1
22                 
23                 if dict1[l1Num] == 0 {
24                     dict1[l1Num] = nil
25                 }
26                 
27                 l1 += 1
28             }
29             
30             while dict2.keys.count >= K {
31                 let l2Num = A[l2]
32                 dict2[l2Num]! -= 1
33                 
34                 if dict2[l2Num] == 0 {
35                     dict2[l2Num] = nil
36                 }
37                 
38                 l2 += 1
39             }
40             
41             count += l2 - l1
42 
43             r += 1
44         }
45         
46         return count
47     }
48 }