題目描述:給定整數陣列 cards,找出包含至少兩張相同數字卡片的最短連續子陣列(子陣列需涵蓋兩張重複牌),回傳其長度。若不存在任何重複牌,回傳 -1。
解題思路:使用可變大小滑動視窗,搭配 unordered_map 記錄視窗內每個值最近一次出現的索引。右指針 right 持續右移:若 cards[right] 在 map 中已有記錄(代表視窗內存在與之相同的牌),則以 right - lastIndex + 1 更新最小長度,其中 lastIndex 為該值上一次出現的索引——因為這兩張相同的牌之間的子陣列即為一個合法窗口,且長度最小。更新完後,將 cards[right] 的記錄更新為當前索引 right(向右推進,確保下一次找到的是更短的區間)。由於每個重複對都對應兩個端點,只需追蹤「最近的前一個相同元素」即可,不需真正維護視窗的左邊界——每次發現重複時,兩個相同元素的位置就確定了子陣列的邊界。
時間複雜度:O(n) — 單次線性掃描陣列,每個元素進行一次 HashMap 查詢與更新,均為平均 O(1),整體平均 O(n)。
空間複雜度:O(min(n, v)) — HashMap 最多存放 n 個不同元素,其中 v 為元素值域大小,空間為 O(min(n, v))。
1. Initialize lastIndex = empty map, minLen = infinity.
2. For right from 0 to n-1:
a. Let val = cards[right].
b. If val exists in lastIndex:
- Compute len = right - lastIndex[val] + 1.
- Update minLen = min(minLen, len).
c. Update lastIndex[val] = right.
3. If minLen is still infinity, return -1; otherwise return minLen.方法一:HashMap 記錄最近索引(最優解) — 如本題解,平均時間 O(n)、空間 O(n)。只記錄每個值的最近一次出現位置,保證每次找到的重複對距離最小。
方法二:滑動視窗 + HashMap 計數 — 維護左指針和右指針,用 unordered_map<int,int> 記錄視窗內每個值的出現次數。當某個值的計數達到 2 時,記錄視窗長度並將左指針右移直到移除其中一個重複元素。時間 O(n)、空間 O(n)。邏輯等價但實作較繁瑣,每次需逐步移動左指針。
方法三:排序 + 逐對掃描 — 先將 (value, index) 配對後按值排序,再逐一比對相同值的相鄰索引對,計算最小距離加一。時間 O(n log n)、空間 O(n)。邏輯清晰但有額外排序開銷,不如直接用 HashMap。