UVa11536 - Smallest Sub-Array

出處:https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=2531

解題策略(一):每次加入一個數字到最後,同時檢查是否1到K所有數字都有了,

如果是,則依序刪除區間最左邊的數字,如果大於K的數字直接忽略,小於K的則計算目前該數字的個數

,如果只剩一個,則刪除後區間內該數字就不存在,則刪除後停止繼續刪除。

解題策略(二):速度慢且浪費空間,容易理解

將所有數字加入deque,每次加入一個數字到最後,計算1到K每一個數字的出現次數

,並計算是否已經有1到K的所有數字,若是則從最左邊依序刪除數字直到1到K中的一個數字不存在,

刪除過程中不斷更新,有1到K每一個數字的最小區間