演算法 - 尺取法

適用題型

在給定的一組數據 中找到不大於頰一個上限的”最優連續子序列”

核心思想

尺取法是雙指標的應用類型，用兩個指標保存選取區間的左右端點，並且依據題目的條件不斷推進區間的左右端點，直到遍歷剛整個數組為止。

尺取法又被戲稱為蟲取法，因為遍歷的過程和毛毛蟲爬行的過程很相似。

注意事項

使用尺取法時應清楚以下四點：

1. 什麼情況適用尺取法
2. 何時推進區間的端點
3. 如何推進區間的端點
4. 何時結束區間的枚舉

例題

給定一個正整數陣列，找出最短的子陣列，其和大於或等於S

分析

首先，序列都是正整數，如果一個區間的和大於或等於S，右端點就不需要再推進了。右端點停止後，左端點開始推進，左端點推進時需要判斷區間之和是否仍符合大於等於S的條件，若是且區間的長度也小於最小子陣列長度時則更新，若否則停止左端點的推進。重覆推進右端點和左端點，直到右端點遍歷至陣列未尾為止。

psesudo-code如下：

1. 右端點推進
2. 右端點是否抵達末尾，若是則結束遍歷，若否則繼續執行。
3. 計算區間和是否大於或等於S
4. 若否，回到步驟1, 若是,繼續步驟5
5. 計算區間長度，小於儲存的子陣列長度時，將之更新為目前的值
6. 左端點推進
7. 計算區間和是否大於或等於S
8. 若否，回到步驟1。若是，回到步驟5。

例題2

給定一個數組，找出一個數字不重覆出現的最長子數組。

分析

用一個字典保存區間內出現過的數字和位置，每次右端點推進時，若數字不存在於字典裡時就更新字典，若數字已存在字典裡時，將左端點移動至該位置+1處並更新該數字於字典裡的位置為右端點，重覆以上步驟直到右端點扺達陣列末尾。