雙指針 - HackMD

## 概念在[基礎概念](/HJTzt0Zdll)已經講過雙指針的概念與應用類型，以下就是拿常見的類型去解說 ## Sliding window 用兩個指標去維護一個區間，然後讓這個區間往左右移動，或是讓區間的大小變動若是區間左右移動，代表兩個指標的相對移動是 $0$，代表都往左移(或都往右移) $i$ 格若是區間大小變動，那代表兩個指標更靠近或更遠了 ### 與題目對應概念由於 Sliding window 的概念是用兩個指標(指針)維護一個區間，區間換句話說也可以是 1. (連續 continue) 子陣列(subarray) 2. (連續 continue) 區段(section) 3. (連續 continue) 子字串(substring) 所以在這些用詞出現的時候，就可以考慮一下是否是 Sliding window 的問題而當題目還多出現以下概念的時候，基本就可以確定是 Sliding window 了 1. 固定長度 $\rightarrow$ 快速更新區間值 2. 可變長度 $\rightarrow$ 動態收縮、擴大區間 3. 區間內特定值出現頻率統計 $\rightarrow$ 與 map 輔助使用 4. 環形處理 $\rightarrow$ 複製陣列 5. 極值維護 $\rightarrow$ 具單調性的資料結構 ### 例題-Leetcode 643. Maximum Average Subarray I 給定一個由 $n$ 個整數組成的陣列`nums`和一個整數 $k$，找出所有長度為 $k$ 的連續子陣列其中的子陣列值平均稱為 $X_i$，求最大的 $X_i$，誤差小於 $10^{-5}$ 的答案都可以這題就是固定長度區間例題，整個區間往右移動就可以計算出所有答案，舉個例子假設原本是區間`nums[0 ~ k-1]`，下一個區間應該是`nums[1 ~ k]`，如果重新計算那每次都需要找 $k$ 個位置，但如果用上一個區間把`nums[0]`減去，再加上`nums[k]` 這樣相當於就是區間`nums[1 ~ k]`，其他區間也可以用同一個辦法推出來 ```cpp= class Solution { public: double findMaxAverage(vector<int>& nums, int k) { double max_n = -100000 ; // 當前最大平均 int p1 = 0, p2 = k-1, sum = 0, len = nums.size() ; for (int i=p1;i<=p2;i++) // 計算第一個區間 sum += nums[i] ; max_n = (double)sum/k ; while (p2<len-1) { // 計算出所有區間 sum = sum - nums[p1++] + nums[++p2] ; double tmp = (double)sum/k ; max_n = (max_n > tmp) ? max_n : tmp ; // 更新最大平均 } return max_n ; } }; ``` ### 例題-Leetcode 209. Minimum Size Subarray Sum 給定一個正整數陣列`nums`和一個正整數`target` 找出一個最短的連續子陣列，使該子陣列的值總和大於等於`target`，如果不存在答案就回傳 $0$ 這題是用可變長度的 Sliding window，整個策略會像是下面敘述的 1. 從最開頭開始長度 $1$ 的區間 2. 如果目前總和小於 $k$，就擴充區間，所以右方的指標往右 3. 如果目前總和大於等於 $k$，就縮減區間(左指標右移)，如果區間已經是 $1$ 了就直接回傳 ```cpp= class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int len = nums.size(), min_len, sum, p1 = 0, p2 = 0 ; min_len = len + 1 ; sum = nums[0] ; while (p2 < len) { if (sum >= target) { // 區間和滿足條件 min_len = min(min_len, p2-p1+1) ; if (p1 < p2) { // 縮減範圍 sum -= nums[p1] ; p1++ ; } else return 1 ; // 最小範圍是 1 } else { if (p2 < len-1) // 擴大範圍 sum += nums[++p2] ; else p2++ ; } } if (min_len == len+1) return 0 ; // 無答案 return min_len ; } }; ``` 這個演算法能成功找出答案的原因是它把右指標當成一種固定終點了導致每次右指標變動的時候，我們都是在求"以右指標作為終點，找出符合條件的連續子陣列" 而右指標一定會走過每個位置 $\rightarrow$ 每個位置作為終點的答案都找出來了最後只要加上簡單的比較就可以知道整個陣列的答案 ### 例題-Leetcode 3. Longest Substring Without Repeating Characters 給定一個字串`S`，找出不含重複字元的最長子字串這題要找不含重複字元的最長子字串，所以區間長度是會變動的因為有"不含重複字元"的條件，所以我們需要紀錄當前區間的每個字母的數量可以用 map(哈希表) 來實作，如果字串中元素只有大小寫字母的話也可以用 `小寫字母-'a'` 作為 index 的方式用 array 紀錄 (其實這題可以用 $256$ 格的 array 處理，但用 map 比較適合學習) 但是這題還有數字、空格等其他元素所以採用哈希表的方式實際的策略其實就兩個 : 1. 如果當前區間會造成重複字元，那就將範圍縮減，左指標右移動直到不含重複字元 2. 前一個步驟做完後當前區間不含重複字元，試圖擴張區間，右指標右移 ```cpp= class Solution { public: int lengthOfLongestSubstring(string s) { vector<int> cnt(26, 0) ; // p1, p2 左右指標、slen 當前子字串長度、max_len 當前答案 int p1 = 0, p2 = 0, len = s.size(), slen = 0, max_len = 1 ; if (len == 0) return 0 ; // 注意空字串的特例 unordered_map<char, int> mp ; mp[s[0]] = 1 ; p2++, slen++ ; while (p2 < len) { // 如果當前區間會造成重複字元 if (mp.find(s[p2]) != mp.end() && mp[s[p2]] == 1) while (mp[s[p2]] == 1) // 縮減區間直到不含重複字元 mp[s[p1++]]--, slen-- ; mp[s[p2]] = 1 ; slen++, p2++ ; // 擴張區間 max_len = max(max_len, slen) ; } return max_len ; } }; ``` 其實透過這兩題變動區間，我想傳達的概念是變動區間有點像是把右指標當成固定終點來看比如這題就是假設以第 $i$ 個字元作為子字串的結尾，找出最長符合條件的子字串因為右指標一定會走過每個字元，那答案就會在某個字元時出現，換句話說最終答案對應的子字串結尾，一定是題目給定的字串終某個字元而 Sliding window 可以找出每個字元做結尾時的答案加上簡單的比較就一定可以找出答案 ### 例題-Leetcode 560. Subarray Sum Equals K 給定一個整數陣列`nums`和一個整數`k`，回傳子陣列總和等於 $k$ 的個數這題雖然看起來跟之前的題目沒什麼兩樣，但其實這裡有兩個要注意的地方 1. 含負數，代表左指標盲目地左移可能是錯誤的 2. 要回傳的不是子陣列的長度，而是總和為 $k$ 的子陣列數量所以我們不能在用之前那種方式去解，這時候我們可以轉換一下思路計算區間和的方法除了一個個慢慢計算之外還有前綴和，前綴和可以透過兩點差值來計算兩點區間和當然這裡有指定區間和要是 $K$，所以我們可以得出下列公式 `prefix[j+1]-prefix[i] = k -> prefix[j+1]-k = prefix[i]` 從這個公式就可以知道，對於某點 $j+1$，我們要找出它之前的所有滿足公式的 $i$ 找的方式也很簡單，一樣用哈希表去記錄哪些前綴和(特定數字)出現過幾次 ```cpp= class Solution { public: int subarraySum(vector<int>& nums, int k) { int len = nums.size() ; vector<int> prefix(len+1, 0) ; // 計算前綴和 for (int i=0;i<len;i++) prefix[i+1] = prefix[i] + nums[i] ; int p1 = 0, p2 = 1, ans = 0 ; unordered_map<int, int> mp ; mp[0] = 1 ; // 注意前綴和的第一個元素是 0 while (p2 <= len) { int tmp = prefix[p2] - k ; // 區間和為 k 的對應前綴和 if (mp.find(tmp) != mp.end()) // 找到了 ans += mp[tmp] ; if (mp.find(prefix[p2]) == mp.end()) // 將前綴和放入 map mp[prefix[p2]] = 0 ; mp[prefix[p2]]++, p2++ ; // 擴充區間 } return ans ; } }; ``` 這題的概念是 Sliding window 在前綴和當中的應用，不過你仔細看就會發現我定義的 $p1$ 完全沒有變動，因為這裡在前墜和的概念是右指標只能在區間`[p1, p2]`找想要的值但實際區間和對應的區間應該是`[x, p2]`，這裡的 $x$ 會限定在區間`[p1, p2]` 內而實際的 $x$ 值我們也不知道，我們只能透過公式+哈希表找到有多少 $x$ 符合條件 ### 例題-Leetcode 239. Sliding Window Maximum 給定一個整數陣列`nums`，有一個大小為 $k$ 的 Sliding window 從陣列的最左邊移到最右邊你只能看到 $k$ 個數字，每次移動 Sliding window 都會向右一個位置把每個 Sliding window 中的最大值存到一個 vector 中回傳這算是比較困難的問題了，如果不同 Sliding window 就重新計算的話，複雜度會是 $O(nk)$ 其實這個問題會涉及到另外一個概念-單調 deque，因為我們不斷往右，且需要最大值我們可以先簡化一下問題，求出一個陣列中某元素 $X$ 左方第一個大於 $X$ 的值對應的位置說的有點複雜，簡單來說假設陣列為`{6,5,4,3}`，那 $3$ 左方第一個大於 $3$ 的數字就是 $4$ 找的方式也很簡單，從左往右找大於 $3$ 的值最後出現在哪裡就好，但是當這個問題拓展了不只要求某一個元素，而是要求多個元素，這個方法就會變得特別沒效率，所以我們轉換一下思路左方大於 $X$ 的第一個值，那我們其實在不確定 $X$ 的情況下，先把所有值都存進去 deque 但是很明顯，假設陣列為`{3,4,x}`，那 $3$ 根本就不需要放進去，可以證明一下 * 假設 $x \ge 4$，那不管是 $4$ 還是"比 $4$ 還小的" $3$ 都沒用 * 假設 $x < 4$，那一樣會先找到 $4$ 由此可知，維護這個簡化後問題的單調 deque 就需要保證幾點 1. 如果當前數字大於等於之前 deque 存的值，把那些值都丟掉(因為用不到)，然後放入當前數字 2. 如果當前數字小於之前 deque 存的值，由於不確定 $x$ 的大小，所以當前數字直接存入 deque 回到原本的題目，由於我們多了一個 Sliding window，所以這個還需要確保數字在範圍內所以每次移動都要判斷 deque 最左方(相對最早進入)的值是否已經在範圍外了基於這個原因，我們應該儲存 index，因為 index 可以判斷是否在範圍外，也可以找出值 ```cpp= class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> dq ; vector<int> result ; int len = nums.size() ; for (int i=0;i<len;i++) { // 確保數字還在 Sliding window 範圍內 if (!dq.empty() && dq.front() == i-k) dq.pop_front() ; // 去除比當前數字還小的值 while(!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back() ; // 儲存當前數的 index dq.push_back(i) ; if (i >= k-1) // 將當前最大值放入答案 result.push_back(nums[dq.front()]) ; } return result ; } }; ``` ## 相向指針相向指針就是互相靠近的雙指針，基本上會有三個使用前提 1. 資料是可排序/已排序的 2. 可以透過"縮小範圍"來找出最終的答案 3. 單調性條件成立其實第一個跟第三個可以當作是一樣的而單調性也是大部分題目可以用相向指針解題的關鍵 ### 與題目對應概念 * 與 $K$ 值相同的兩/三數和 * 最小差值、與 $K$ 值相近... * 長短不一找最大面積長方形 * 區間合併 * 字串操作基本上前四個有的就可以考慮看看是否可以用相向指針去解最後一個字串操作可能是迴文、反轉之類的，相對比較直觀 ### Leetcode 167. Two Sum II – Input Array Is Sorted {%hackmd Hyxk8LAT0 %} ### Leetcode 15. 3Sum {%hackmd Bk05L_Njlx %} ### Leetcode 16. 3Sum Closest {%hackmd S1aY0ANjxe %}