Leetcode-992 Subarrays with K Differant Integers

题目描述

https://leetcode.com/problems/subarrays-with-k-different-integers/

给定一个数组 A,求有 k 个不同元素组成的子数组个数。

例如:

1
2
3
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].

测试用例

根据题意,数组长度 n 的取值区间为 [1, 20000],数组元素取值区间为 [1, n],说明最多可能有 n 个不同元素,k 取值区间也是 [1, n],需要考虑 k > count(distinct A[i]) 的情况。考虑如下测试用例:

1
2
3
4
5
6
// Case 0: k > count(distinct A[i])
A = [1, 1, 1, 1, 1], k = 2
Output: 0
// Case 1: k == count(distinct A[i])
A = [1, 1, 2, 3], k = 3
// Case 2: k < count(distinct A[i])

分析

第一眼看应该是使用滑窗,根据之前的总结滑窗的模板如下

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def slidingWindowTemplate(s, t):
# 定义其他变量,存储结果,存储判断条件等变量
begin = end = 0

while f(end): # case 1: slide end
# do something
end += 1
while g(): # case 2: slide begin
# do something
begin += 1

# meet some condition

使用滑窗需要思考两个问题:

  1. 什么时候滑动 end 指针?
  2. 什么时候滑动 begin 指针?

经过思考直接求解不好求,我们换个思路:最多包含 k 个不同元素的子数组有多少个?滑窗 + HashMap 是解决这类问题最常用的方案。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def atMostKDistinct(A, k):
begin = end = 0
window = collections.defaultdict(int)
n, distinct = len(A), 0 # distinct indicate count of sliding window
ans = 0

while end < n:
e = A[end]
if window[e] == 0:
distinct += 1
window[e] += 1
end += 1
while distinct > k:
b = A[begin]
window[b] -= 1
if window[b] == 0:
distinct -= 1
begin += 1
# [begin, end) has end - begin items that is numbers of subarray end of A[end]
ans += end - begin
return ans

记 f(k) 为小于等于 k 个不同元素的子数组个数,则 f(k-1) 为小于等于 k - 1 个不同元素的子数组个数。所以,确切的有 k 个不同元素的子数组个数 = f(k) - f(k-1)。

代码

根据如上分析,完整代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
def subarraysWithKDistinct(self, A: List[int], k: int) -> int:
def atMostKDistinct(k):
begin = end = 0
window = collections.defaultdict(int)
n, distinct = len(A), 0 # distinct indicate count of sliding window
ans = 0

while end < n:
e = A[end]
if window[e] == 0:
distinct += 1
window[e] += 1
end += 1
while distinct > k:
b = A[begin]
window[b] -= 1
if window[b] == 0:
distinct -= 1
begin += 1
# [begin, end) has end - begin items that is end - begin subarrays
ans += end - begin
return ans
return atMostKDistinct(k) - atMostKDistinct(k-1)

在 [begin, end) 区间中,以 A[end-1] 结尾的子数组个数是 end - begin,所以 ans += end - begin

相关题目 - https://leetcode.com/problems/count-number-of-nice-subarrays/

本文标题:Leetcode-992 Subarrays with K Differant Integers

文章作者:Pylon, Syncher

发布时间:2019年11月04日 - 23:11

最后更新:2023年03月11日 - 17:03

原始链接:https://0x400.com/fundamental/algorithm/lc-992-subarrays-with-k-different-integers/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。