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 = [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. 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 个不同的整数：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. 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 }