一，定義

雙指針?biāo)惴ㄊ且环N常用于解決數(shù)組和鏈表問題的算法技巧。它的核心思想是使用兩個(gè)指針在數(shù)據(jù)結(jié)構(gòu)中按照一定的規(guī)則移動(dòng)，從而達(dá)到快速搜索或處理數(shù)據(jù)的目的。這個(gè)技巧通常用于優(yōu)化算法，降低時(shí)間復(fù)雜度，提高程序的執(zhí)行效率。雙指針?biāo)惴ㄓ卸喾N應(yīng)用場(chǎng)景，以下是其中一些常見的情況：

1. 快慢指針：在鏈表中，快慢指針常用于判斷是否存在環(huán)，找到環(huán)的起點(diǎn)，以及求解中位數(shù)等問題?？熘羔樏看我苿?dòng)兩步，慢指針每次移動(dòng)一步，它們會(huì)以不同的速度遍歷鏈表，從而實(shí)現(xiàn)一些特定的目標(biāo)。

2. 左右指針：在數(shù)組或字符串中，左右指針常用于搜索滿足某種條件的元素。左指針從開頭開始，右指針從末尾開始，它們根據(jù)問題的要求逐漸向中間靠攏，通常在搜索有序數(shù)組或字符串中的元素時(shí)非常高效。

3. 對(duì)撞指針：在有序數(shù)組中查找兩個(gè)數(shù)的和等于特定值，對(duì)撞指針是一種常見的解決方法。左指針從開頭開始，右指針從末尾開始，它們根據(jù)和的大小逐漸接近目標(biāo)值。

雙指針?biāo)惴ǖ膬?yōu)點(diǎn)在于它通常具有較低的空間復(fù)雜度，因?yàn)樗恍枰鎯?chǔ)兩個(gè)指針。同時(shí)，雙指針?biāo)惴ǖ臅r(shí)間復(fù)雜度通常較低，因?yàn)樗鼈冊(cè)诒闅v過程中減少了不必要的比較和計(jì)算。

簡(jiǎn)單的來看一下雙指針的思想的最常見的兩種思想，快慢指針和對(duì)撞指針兩種方法，實(shí)話說雙指針?biāo)惴ǜ袷且环N模擬的思想，不過是對(duì)工具的模擬來完成的，使用的時(shí)候重點(diǎn) ： 指針和指針?biāo)镁S護(hù)的序列。

圖示

二，常見的雙指針題型

以下是幾個(gè)常見的經(jīng)典雙指針題型：

1. 兩數(shù)之和（Two Sum） ：

   • 題目描述：給定一個(gè)整數(shù)數(shù)組和一個(gè)目標(biāo)值，找出數(shù)組中兩個(gè)數(shù)的和等于目標(biāo)值的索引。
   • 解題思路：使用一個(gè)哈希表來記錄已經(jīng)遍歷過的元素，同時(shí)使用雙指針來查找滿足條件的兩個(gè)數(shù)。

2. 反轉(zhuǎn)字符串（Reverse String） ：

   • 題目描述：給定一個(gè)字符數(shù)組，將其反轉(zhuǎn)。
   • 解題思路：使用雙指針，一個(gè)指向數(shù)組開頭，另一個(gè)指向數(shù)組末尾，然后交換它們指向的元素，直到兩指針相遇。

3. 盛最多水的容器（Container With Most Water） ：

   • 題目描述：給定一組垂直線段，每個(gè)線段的長(zhǎng)度表示該位置的高度，選擇兩個(gè)線段，使得它們和 x 軸構(gòu)成的容器
   • 解題思路：使用雙指針，一個(gè)指向數(shù)組開頭，另一個(gè)指向數(shù)組末尾，然后根據(jù)指針指向的線段高度和寬度計(jì)算容器的面積，并不斷移動(dòng)指針以找到最大面積。

4. 三數(shù)之和（3Sum） ：

   • 題目描述：給定一個(gè)整數(shù)數(shù)組，找出所有不重復(fù)的三元組，使得三元組的和等于零。
   • 解題思路：使用雙指針，首先將數(shù)組排序，然后使用一個(gè)外循環(huán)遍歷數(shù)組中的每個(gè)元素，內(nèi)部使用雙指針來尋找滿足條件的三元組。

5. 合并兩個(gè)有序數(shù)組（Merge Two Sorted Arrays） ：

   • 題目描述：給定兩個(gè)有序整數(shù)數(shù)組，將它們合并成一個(gè)有序數(shù)組。
   • 解題思路：使用雙指針，一個(gè)指向第一個(gè)數(shù)組的末尾，另一個(gè)指向第二個(gè)數(shù)組的末尾，然后從后向前合并數(shù)組中的元素。

6. 最長(zhǎng)回文子串（Longest Palindromic Substring） ：

   • 題目描述：給定一個(gè)字符串，找出最長(zhǎng)的回文子串。
   • 解題思路：使用雙指針，從每個(gè)字符向兩側(cè)擴(kuò)展，同時(shí)檢查擴(kuò)展后的子串是否是回文，記錄最長(zhǎng)的回文子串。

三 ，解題常見的模型
一般的雙指針?biāo)惴ǖ乃悸肥腔谙嚓P(guān)的循環(huán)上面的，所以我們一般的雙指針?biāo)惴ǘ际悄軌虮容^簡(jiǎn)單的，并且雙指針?biāo)惴ㄊ且环N基本的算法思路沒有具體的模板可以直接實(shí)現(xiàn)，所以不再給出代碼實(shí)現(xiàn)。