雙指針?biāo)枷?/h1>

? 簡單來講，雙指針?biāo)枷胧侵冈诒闅v對象的過程中，使用兩個(gè)指針----相同方向（快慢指針）、不同方向（對撞指針），進(jìn)行掃描，尋找滿足題目要求的條件，從而降低時(shí)間復(fù)雜度的算法。

? 雙指針?biāo)枷胧呛芏嗨惴ǖ幕A(chǔ)，如歸并排序、滑動窗口、字符匹配等。

??

對撞指針通常適用于：

• 有序數(shù)組、有序鏈表，從中尋找滿足條件的組合

• 可能是一對數(shù)、三個(gè)數(shù)或子數(shù)組
  

快慢指針通常用于：

• 問題需要處理環(huán)上的問題，比如環(huán)形鏈表和環(huán)形數(shù)組

• 當(dāng)你需要知道鏈表的長度或是某個(gè)特別位置的信息的時(shí)候

例題：

對撞指針：

題解：

快慢指針：

? 題解：

? 數(shù)組已經(jīng)有序，并且要求使用原地算法，只要輸出新數(shù)組的長度即可，多余的部分不做考慮。因此我們定義left，right左右兩個(gè)快慢指針：

• 快指針先遍歷，當(dāng)遇到不重復(fù)的元素時(shí)，慢指針向前移動一步。

• 將快指針當(dāng)前的元素復(fù)制到慢指針位置，繼續(xù)遍歷。

• 最后返回 left+1。

參考：

https://zhuanlan.zhihu.com/p/104983442