演算法筆記系列 — 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 有沒有循環的相關題目：
如果你覺得這篇文章對你有幫助，歡迎買杯咖啡贊助 ☕️ 謝謝
