又是一波總結
相信大家已經對雙指標法很熟悉了，但是雙指標法並不隸屬於某一種
資料結構
，我們在講解陣列，連結串列，字串都用到了雙指標法，所有有必要針對雙指標法做一個總結。
陣列篇
在陣列：就移除個元素很難麼？中，原地移除陣列上的元素，我們說到了陣列上的元素，不能真正的刪除，只能覆蓋。
一些同學可能會寫出如下程式碼（
虛擬碼
）：
for （int i = 0； i < array。size（）； i++） {
if （array［i］ == target） {
array。erase（i）；
}
}
這個程式碼看上去好像是O（n）的時間
複雜度
，其實是O（n^2）的時間複雜度，因為erase操作也是O（n）的操作。
所以此時使用雙指標法才展現出效率的優勢：
「透過兩個指標在一個for迴圈下完成兩個for迴圈的工作。」
字串篇
在字串：這道題目，使用庫函式一行程式碼搞定中講解了反轉字串，注意這裡強調要原地反轉，要不然就失去了題目的意義。
使用雙指標法，
「定義兩個指標（也可以說是索引下表），一個從字串前面，一個從字串後面，兩個指標同時向中間移動，並交換元素。」
，時間複雜度是O（n）。
在替換空格 中介紹使用雙指標填充字串的方法，如果想把這道題目做到極致，就不要只用額外的輔助空間了！
思路就是
「首先擴充陣列到每個空格替換成"%20"之後的大小。然後雙指標從後向前替換空格。」
有同學問了，為什麼要從後向前填充，從前向後填充不行麼？
從前向後填充就是O（n^2）的演算法了，因為每次新增元素都要將新增元素之後的所有元素向後移動。
「其實很多陣列（字串）填充類的問題，都可以先預先給陣列擴容帶填充後的大小，然後在從後向前進行操作。」
那麼在字串：花式反轉還不夠！中，我們使用雙指標法，用O（n）的時間複雜度完成字串刪除類的操作，因為題目要產出冗餘空格。
「在刪除冗餘空格的過程中，如果不注意程式碼效率，很容易寫成了O(n^2)的時間複雜度。其實使用雙指標法O(n)就可以搞定。」
「主要還是大家用erase用的比較隨意，一定要注意for迴圈下用erase的情況，一般可以用雙指標寫效率更高！」
連結串列篇
翻轉連結串列是現場面試，白紙寫程式碼的好題，考察了候選者對連結串列以及指標的熟悉程度，而且程式碼也不長，適合在白紙上寫。
在連結串列：聽說過兩天反轉連結串列又寫不出來了？中，講如何使用雙指標法來翻轉連結串列，
「只需要改變連結串列的next指標的指向，直接將連結串列反轉 ，而不用重新定義一個新的連結串列。」
思路還是很簡單的，程式碼也不長，但是想在白紙上一次性寫出bugfree的程式碼，並不是容易的事情。
在連結串列中求環，應該是雙指標在連結串列裡最經典的應用，在連結串列：環找到了，那入口呢？中講解了如何透過雙指標判斷是否有環，而且還要找到環的入口。
「使用快慢指標（雙指標法），分別定義 fast 和 slow指標，從頭結點出發，fast指標每次移動兩個節點，slow指標每次移動一個節點，如果 fast 和 slow指標在途中相遇 ，說明這個連結串列有環。」
那麼找到環的入口，其實需要點簡單的數學推理，我在文章中把找環的入口清清楚楚的推理的一遍，如果對找環入口不夠清楚的同學建議自己看一看連結串列：環找到了，那入口呢？。
N數之和篇
在雜湊表：解決了兩數之和，那麼能解決三數之和麼？中，講到使用雜湊法可以解決1。兩數之和的問題
其實使用雙指標也可以解決1。兩數之和的問題，只不過1。兩數之和求的是兩個元素的下標，沒法用雙指標，如果改成求具體兩個元素的數值就可以了，大家可以嘗試用雙指標做一個leetcode上兩數之和的題目，就可以體會到我說的意思了。
使用了雜湊法解決了兩數之和，但是雜湊法並不使用於三數之和！
使用雜湊法的過程中要把符合條件的三元組放進vector中，然後在去去重，這樣是非常費時的，很容易超時，也是三數之和透過率如此之低的根源所在。
去重的過程不好處理，有很多小細節，如果在面試中很難想到位。
時間複雜度可以做到O（n^2），但還是比較費時的，因為不好做剪枝操作。
所以這道題目使用雙指標法才是最為合適的，用雙指標做這道題目才能就能真正體會到，
「透過前後兩個指標不算向中間逼近，在一個for迴圈下完成兩個for迴圈的工作。」
只用雙指標法時間複雜度為O（n^2），但比雜湊法的O（n^2）效率高得多，雜湊法在使用兩層for迴圈的時候，能做的剪枝操作很有限。
在雙指標法：一樣的道理，能解決四數之和中，講到了四數之和，其實思路是一樣的，
「在三數之和的基礎上再套一層for迴圈，依然是使用雙指標法。」
對於三數之和使用雙指標法就是將原本暴力O（n^3）的解法，降為O（n^2）的解法，四數之和的雙指標解法就是將原本暴力O（n^4）的解法，降為O（n^3）的解法。
同樣的道理，五數之和，n數之和都是在這個基礎上累加。
總結
本文中一共介紹了leetcode上九道使用雙指標解決問題的經典題目，除了連結串列一些題目一定要使用雙指標，其他題目都是使用雙指標來提高效率，一般是將O（n^2）的時間複雜度，降為O（n）。
建議大家可以把文中涉及到的題目在好好做一做，琢磨琢磨，基本對雙指標法就不在話下了。
本文：
已經收錄，裡面還有leetcode刷題攻略、各個型別經典題目刷題順序、思維導圖，
可以fork到自己倉庫
，有空看一看一定會有所收穫，如果對你有幫助也
給一個star支援一下吧！
我的B站（裡面有我講解的演算法影片已經程式設計相關知識）：
我是程式設計師Carl，哈工大師兄，先後在騰訊和百度從事技術研發多年，利用工作之餘重刷leetcode，更多精彩演算法文章盡在：程式碼隨想錄，關注後，回覆「Java」「C++」「python」「簡歷模板」等等，有我整理多年的學習資料，可以加我微信，備註「個人簡介」+「組隊刷題」，拉你進入刷題群（無任何廣告，純個人分享），每天一道經典題目分析，我選的每一道題目都不是孤立的，而是由淺入深一脈相承的，如果跟住節奏每篇連續著看，定會融會貫通。
