演算法筆記系列 — Two Pointer 與Sliding Window
Two Pointer 與 Sliding Window 都是蠻常聽到的一種解題常用的技巧,也可以說是演算法的解題 pattern。而 Two Pointer 又可以分為左右指標與快慢指標兩種,Sliding Window 則可以算是廣義的左右指標中的一種。
Two Pointer 我們最常見於 Array 、String 或是 Linked-List 中使用,常常我們會拿來用來做特並條件下的搜尋或是總和計算。然而,使用 Two Pointer 的方法,可以帶來什麼好處呢?在通常的情況下,可以讓執行時間複雜度保持在線性的時間複雜度 O(n),大大的降低運算時間。
左右指標
左右指標多用於 Array 或是 String,其概念就是設定左右兩個指標,在適當情況與條件下,移動其中的一個或兩個指標,來找到標值或是做一些總和的計算。而兩個指標的方向可以是同方向,也可以是反方向移動,端看當下的情境需求。
Sliding Window
Sliding Window 可以算是廣義的左右指標中的一種,但是在某些情況下,Sliding Window 可以只使用一個 point 與 一個 window size 來實作,並不用真正使用到兩個指標。
而 Sliding Window 的 pattern 常用 window 內的所有 element 來解題,例如透過每回合操作 window 內的總和,來達到解題的目的。而 Two Pointer 通常用於操作兩個 pointer 上的值,透過兩個指標的值再去做更多的運算或是判斷來解題。不過自己認為兩者個概念是很相近的,也不用太糾結在到底是哪一個 pattern。
實際應用
我們來看看這題,11. Container With Most Water
題目:找出兩兩垂直線畫出的空間,可以容納的水量最大
暴力法:最直覺的暴力法就是兩個 for 迴圈,兩兩比較找出容量最大值,但想當然這絕對不是一個好作法。
左右指標:換個方式想,如果我們從最外圍往內框住來往內尋找,每次檢查兩根垂直線,每次往內走把短的換掉,直到兩個指標重疊,就可以以最快的方式走完整個 Container 了。
簡單描述一下,這張圖由左上、左下,右上然後到右下這樣的順序來看:
- 把兩個指標分別設定在兩端,index 0 與 8, 可以得到目前的最大容量為 8
1*(8-0)
- 接著挑比較短的指標移動,index 0 → 1,最大容量為 49
- 再繼續挑比較短的指標,index 8 → 7,最大容量為 18
- 持續做到整個 Array 都找完為止
實際的程式如下:
其他相似可以用左右指標解題的題目,還可以參考:
- 3. Longest Substring Without Repeating Characters
- 26. Remove Duplicates from Sorted Array
- 80. Remove Duplicates from Sorted Array II
- 167. Two Sum II — Input array is sorted
- 209. Minimum Size Subarray Sum
- 977. Squares of a Sorted Array
快慢指標
快慢指標多用於 Linked-List 的問題,透過 slow 與 fast 兩根指標,讓兩個指標保持一定的間隔規律,通常可以用於解決以下幾種問題:
- 找到 Linked-List 中心點
- 找到 Linked-List 倒數第 K 個節點
- 判斷一個 Linked-List 有沒有循環
舉例來說,在一個 Linked-List 有著兩個指標 slow and fast,每次 slow 走一步,而 fast 走兩步:
找到 Linked-List 中心點
當現在有一個 Linked-List,我們要如何找到中心點呢?比較直覺的暴力法,就是先把整個 List 走完一遍,計算出長度後,再去找中心點的位置。
使用 Fast and Slow Pointer 的解法其實也不會太難想,當你有兩個指標同時移動,慢的一次走一步,快的一次走兩步,當 fast pointer 抵達尾端的時候, slow pointer 就會是在中間的位置。
找尋中心點相關的題目可以參考:
找到 Linked-List 倒數第 K 個節點
另一個常見的問題,找到 Linked-List 倒數第 K 個節點,暴力法也是要先把整個 List 走完一遍,計算出長度後,再去找倒數第 K 個節點的位置。
同樣地,使用 Fast and Slow Pointer 的解法,我們可以先讓 fast pointer 先走 K 步,然後 Slow and Fast 兩個指標再使用一樣的速率前進,當 fast pointer 抵達尾端的時候, slow pointer 就會是在倒數第 K 個節點的位置。
與找到 Linked-List 倒數第 K 個節點的相關題目可以參考:
判斷一個 Linked-List 有沒有循環
要判斷一個 Linked-List 有沒有循環的概念其實也蠻好想,當兩個 Fast and Slow Pointer 走的步數不一樣時,假如有一個循環的時候,兩個指標終究會遇上,就像賽跑被倒追一圈一樣類似的概念。
判斷一個 Linked-List 有沒有循環的相關題目: