題目出處
2260. Minimum Consecutive Cards to Pick Up
難度
medium
個人範例程式碼
class Solution:
def minimumCardPickup(self, cards: List[int]) -> int:
visited = set()
min_window = float("inf")
slow, fast = 0, 0
for fast, card in enumerate(cards):
if card not in visited:
visited.add(card)
else:
while card in visited:
visited.remove(cards[slow])
slow += 1
visited.add(card)
min_window = min(min_window, len(visited) + 1) # add duplicate
return -1 if min_window == float("inf") else min_window
最近在練習程式碼本身就可以自解釋的 Coding style,可以嘗試直接閱讀程式碼理解
算法說明
用同向的 two pointers slow, fast 控制頭尾,
控制 sliding window 的移動
fast 往前走,slow 走在後,
發現有重複的項目時,slow 一直 pop 直到去掉重複
計算 window 大小時,計算 fast-slow+2 (+1 是範圍的關係,+1 是計算去掉的重複項)
input handling
如果沒有找到結果,回傳 -1
(沒有重複文字的 window)
Boundary conditions
控制 fast for-loop 的範圍