|
class Solution(object):
def subarraysWithKDistinct(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
# 904题的进阶，904是寻找最长，这里限定了种类个数k
# 这里涉及到状态回缩
# end在for循环里自动更新，end每次只能在当前位置或者当前位置之后，不能回缩
# 此题出现了恰好等于的情况，k,就需要回缩了，start往后，end往前可以出现一个新的窗口，这个新的窗口我们也需要考虑
# 种类为k，前缀和的思路
# 904题<=2用不回缩的方式写，这里等于k也可以用不回缩的方式写，用904不回缩的方式写，然后<=2 - <=1就可以得到=2的
def leK(nums, k):
start = 0
# 种类的时候放到字典，哈希表中存储
adict = {}
count = 0
for end in range(len(nums)):
if nums[end] not in adict:
adict[nums[end]] = 1
else:
adict[nums[end]] += 1
while len(adict) > k:
adict[nums[start]] -= 1
if adict[nums[start]] == 0:
del adict[nums[start]]
start += 1
# 这里的count有讲究
count += end-start+1
return count
return leK(nums, k) - leK(nums, k-1)
|
