k个不同整数的子数组
2021-11-7-K个不同整数子数组
给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定不同的子数组为好子数组。
（例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。）
返回 A 中好子数组的数目。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/subarrays-with-k-different-integers 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路 set, 加2个for
def f(A, k):
N = len(A)
ans = 0
for i in range(N+1):
for j in range(i):
a = tuple(A[x] for x in range(j,i))
if len(set(a)) == k:
ans += 1
return ans
print(f([1,2,1,2,3], 2))
print(f([1,2,1,3,4],3))
超时
def f(A, k):
import collections
L1 = collections.defaultdict(int)
L2 = collections.defaultdict(int)
l1 = 0
l2 = 0
ans = 0
total1 = 0
total2 = 0
for i,v in enumerate(A):
if L1[v] == 0:
total1 += 1
L1[v] += 1
while total1 > k:
L1[A[l1]] -= 1
if L1[A[l1]] == 0:
total1 -= 1
l1 += 1
if L2[v] == 0:
total2 += 1
L2[v] += 1
while total2 > k-1:
L2[A[l2]] -= 1
if L2[A[l2]] == 0:
total2 -= 1
l2 += 1
ans += l2 - l1
return ans
应该维持一个窗口
来了一个,就要收缩
