992. K 個不同整數的子陣列
給定一個正整數陣列 A，如果 A 的某個子陣列中不同整數的個數恰好為 K，則稱 A 的這個連續、不一定獨立的子陣列為好子陣列，
（例如，[1,2,3,1,2] 中有 3 個不同的整數：1，2，以及 3，）
回傳 A 中好子陣列的數目，
解題：雙指標
看到子陣列，首選雙指標，然后暴力解
（兩個回圈，判斷計數）
class Solution:
def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
left = right = tmp = res = 0
sets = set()
while left < len(A):
while (len(sets)) <= K and right < len(A):
sets.add(A[right])
right += 1
if len(sets) == K:
res += 1
sets = set()
left += 1
right = left
return res
但是這并沒有通過測驗案例，因超出了時間限制
然后我們發現這樣的暴力解法確實太粗糙了
（1）首先我們每一次計數前都有一個判斷，其實這個判斷的條件很大程度上是涵蓋在回圈的條件里的，這意味著每個小回圈都幾乎多判斷一次
（2）每次移動左指標時我們都重置了右指標即上一輪資料，但其實大可不必，因為K值固定，所以我們可以繼承上一輪資料，優化演算法
優化：滑動視窗
（這里未給出需要呼叫的庫）
class Solution:
def subarraysWithKDistinct(self, A: List[int], K: int) -> int:
def helper(A, K):
n = len(A)
i = 0
res = 0
diff_nums = 0
counter = collections.defaultdict(int)
for j in range(n):
counter[A[j]] += 1
if counter[A[j]] == 1:
diff_nums += 1
while diff_nums > K:
res += n - j
counter[A[i]] -= 1
if counter[A[i]] == 0:
diff_nums -= 1
i += 1
return res
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/258531.html
標籤：其他
下一篇：ubuntu常用命令匯總