筆者這些天終于達成了只狼的全成就，甚是歡喜。然而樂極生悲，最近做了些算法題，竟沒有一道靠自己做出來。

感覺算法題常常用到“雙指針法”呢……為什么到現在我還是做不出來這些算法題……

今天就來試著總結一下它的使用場景吧。

---

快慢指針法

又名為“同向指針”，常見于“原地修改數組”的情況。LeetCode.283的移動零就需要通過快慢指針來實現。

題目要求將數組中所有的0移動到末尾。但是我們習慣于數組中數據前移的操作，所以我們將問題轉換為“將非零數據前移并在末尾填充0”。

而快慢指針天然適用于這種場景：快指針跳過無用數據快速遍歷，慢指針從頭到尾依次遞增方便數據覆蓋。簡單來說就是快指針的元素覆蓋慢指針的元素。

這樣一來，前移時，一個指針存放需要前移的元素（快指針），一個指針存放需要被覆蓋的位置（慢指針）。最后快指針到達終點時，慢指針未遍歷的元素數量就是快指針跳過的元素數量。

這里以LeetCode.80刪除有序數組中的重復項為例。

不同于LeetCode.26的元素只出現一次，這里需要能夠存放兩個元素。那么對于這種原地修改數組的問題，我們依舊采用前指針覆蓋后指針的策略。對于第26題，后指針作為被覆蓋的元素，其移動受制于前指針是否發現新的不重復元素。而80題的后指針移動，不光受制于元素的不重復，也受制于后指針的前面是否夠兩個重復元素，如果有，就覆蓋（始終從后指針的角度考慮，那些元素該保留，那些元素該被覆蓋）。

class?Solution?{
public:int?removeDuplicates(vector<int>& nums)?{int?x =?0;int?y =?0;while(y < nums.size()){if(y <=?1){++x;}//因為元素有序，通過x-2判斷同時保證了元素成功前移else?if(y >?1?&& nums[x-2] != nums[y]){nums[x] = nums[y];++x;}++y;}return?x;}
};

相向指針法

兩指針對向行駛，常見于“反轉元素”的情況。LeetCode.345的反轉元音字母。如果用while迭代的話，在處理完后記得讓指針繼續行駛。

相向指針法也常常會與“貪心算法”的思想結合。常常作為條件來判斷指針移動的時機。經典的是“盛水體積”問題，每次選擇最短的木板移動。因為我們確定，局部的選擇短板移動最終促成整體能夠找到體積最大的狀態（移動長板必定變小）。

這里以LeetCode.680驗證回文串為例，題目要求最多刪除一個字符，其能夠成為回文串。這種對稱的結構天然適合對向指針，只要兩邊一樣就讓兩個指針行駛。

但如果兩邊字符不一樣呢？最多刪除一次的限制，我們應該考慮怎樣的局部最優解能最終得出回文串。此時，若刪除字符后剩余的字符串是回文串即可，那最終就是回文串。

class?Solution?{
public:bool?validPalindrome(string?s)?{int?left =?0;int?right = s.size() -?1;bool?canChange =?true;while(left < right){if(s[left] == s[right]){++left;--right;}else{//兩端不一樣時，需要查看兩種刪除的情況return?check(s, left +?1, right) || check(s, left, right -?1);}}//到最后就是普通回文串的情況return?true;}//新建函數判斷普通的回文串bool?check(string?s,?int?left,?int?right){for(int?i = left, j = right; i < j; ++i, --j){if(s[i] != s[j]){return?false;}}return?true;}
};

???????但還有一種情況是需要我們先轉化之后再使用對向指針的類型。比如經典的三數之和。

如果是兩數之和的話，可以直接使用雙指針解開。按照這個思路，三數之和的話，固定一個數，那么剩余就是兩數之和等于這個數的負數的問題。就這樣繼續用雙指針。

class?Solution?{
public:vector<vector<int>>?threeSum(vector<int>& nums) {vector<vector<int>> vec;sort(nums.begin(), nums.end());for(int?i =?0; i < nums.size() -?2?&& nums[i] <=?0; i++){if(i >?0?&& nums[i] == nums[i -?1]){continue;}int?left = i +?1;int?right = nums.size() -?1;int?target = -nums[i];while(left < right){//去重if(left > i +?1?&& nums[left] == nums[left -?1]){++left;continue;}int?sum = nums[left] + nums[right];if(sum == target){vec.push_back({nums[i], nums[left], nums[right]});++left;--right;}else?if(sum < target){++left;}else{--right;}}}return?vec;}
};

???????還有LeetCode.42的接雨水問題，這類問題的輸出總是與兩端元素的變化有關系，就需要考慮使用相向指針法解決。

滑動窗口

滑動窗口是一種較為特殊的同向指針，它通過兩個指針來維護一個窗口，這個“窗口”通常是具有某種性質的連續元素或子串。

比較經典的就是無重復字符串的最長子串。前后指針從起點出發，前指針用于擴展窗口，并每次檢測窗口“無重復字符”的性質是否改變。后指針用于收縮窗口，當字符開始出現重復，則進行收縮，當性質滿足時，繼續前指針擴展。這樣一來，便可以遍歷所有無重復字符的子串。

class?Solution?{
public:int?lengthOfLongestSubstring(string s)?{int?left =?0;int?right =?0;int?length =?0;int?maxLength =?0;vector<char> chars;bool?skip =?false;while(right < s.size()){char?cur = s[right];for(auto?c : chars){if(c == cur){//刪除第一個元素chars.erase(chars.begin());++left;length = right - left;skip =?true;//這里的continue對for起作用，不對while起作用break;}}if(skip){skip =?false;continue;}chars.push_back(cur);++right;length = right - left;if(length > maxLength){maxLength = length;}}return?maxLength;}};

???????需要注意的是，for中的continue不對外部的while起作用。

現在以這道簡單題為例，寫一下滑動窗口的解法。

class?Solution?{
public:double?findMaxAverage(vector<int>& nums,?int?k)?{int?left =?0;int?right = k -?1;int?sum =?0;for(int?i =?0; i < k; i++){sum += nums[i];}int?maxSum = sum;while(right +?1?< nums.size()){int?newSum = sum - nums[left] + nums[right +?1];if(newSum > maxSum){maxSum = newSum;} ? ? ? ? ? ?sum = newSum;++left;++right;}return?(double)maxSum/k;}
};

---

小結

這便是雙指針的3種常見使用方式。

如有補充交流歡迎留言，我們下次再見~