• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

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

原作者: [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: 12, 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. 1 <= A.length <= 20000
  2. 1 <= A[i] <= A.length
  3. 1 <= K <= A.length

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

(例如,[1,2,3,1,2] 中有 3 个不同的整数:12,以及 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. 1 <= A.length <= 20000
  2. 1 <= A[i] <= A.length
  3. 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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
swift的值类型和引用类型发布时间:2022-07-13
下一篇:
iOS(swift)storyboard的国际化(本地化,全球化,多语言)发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap