題目出處

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 的範圍

Reference

• [Python] O(n) time & space, by using dict