什么是雙指針？其實(shí)很好理解，雙指針是一種思想，一種技巧或一種方法，并不是什么特別具體的算法，在二分查找等算法中經(jīng)常用到這個技巧。具體就是用兩個變量動態(tài)存儲兩個或多個結(jié)點(diǎn)，來方便我們進(jìn)行一些操作。通常用在線性的數(shù)據(jù)結(jié)構(gòu)中，比如鏈表和數(shù)組，有時候也會用在圖算法中。

在我們遇到像數(shù)組，鏈表這類數(shù)據(jù)結(jié)構(gòu)的算法題目的時候，應(yīng)該要想得到雙指針的套路來解決問題。特別是鏈表類的題目，經(jīng)常需要用到兩個或多個指針配合來記憶鏈表上的節(jié)點(diǎn)，完成某些操作。鏈表這種數(shù)據(jù)結(jié)構(gòu)也是樹形結(jié)構(gòu)和圖的原型，所以有時候在關(guān)于圖和樹形結(jié)構(gòu)的算法題目中也會用到雙指針。

一、概述

雙指針是一種簡單而又靈活的技巧和思想，單獨(dú)使用可以輕松解決一些特定問題，和其他算法結(jié)合也能發(fā)揮多樣的用處。

雙指針顧名思義，就是同時使用兩個指針，在序列、鏈表結(jié)構(gòu)上指向的是位置，在樹、圖結(jié)構(gòu)中指向的是節(jié)點(diǎn)，通過或同向移動，或相向移動來維護(hù)、統(tǒng)計(jì)信息。

雙指針是指在遍歷對象時，使用兩個或多個指針進(jìn)行遍歷及相應(yīng)的操作。大多用于數(shù)組操作，這利用了數(shù)組連序性的特點(diǎn)。雙指針常用來降低算法的時間復(fù)雜度，因?yàn)槭褂脙蓚€指針可以避免多層循環(huán)。

雙指針的三個關(guān)鍵點(diǎn)：

（1）指針的起始位置的選取

（2）指針的移動方向

（3）指針的移動速度

這三個關(guān)鍵點(diǎn)是雙指針?biāo)惴ǖ暮诵囊彩请y點(diǎn)，

二、算法題型

在時間或空間條件有限的情況下使用單向遍歷需要消耗大量的時間或者根本無法解決問題，這時候就需要我們使用雙指針，通過指針的碰撞判斷是否達(dá)到條件，從而解決問題。

（一）左右指針

左右指針通常在數(shù)組有序的情況下，從最小和最大端同時對數(shù)組進(jìn)行處理，對滿足特定條件的數(shù)組元素進(jìn)行成對處理，快慢指針逐漸靠攏直至發(fā)生碰撞，則遍歷完所有數(shù)組。

舉個例子：

一個孤島上有7個人重量54kg，55kg，56kg，57kg，58kg，59kg，70kg。她們需要逃生到安全的地方?，F(xiàn)在有足夠的救生艇，但是每個救生艇只能坐兩個人，而且每個救生艇最大能承受113kg的重量，那她們最少需要多少救生艇才能全部逃生。

現(xiàn)在我們來分析，如果最重的人可以與最輕的人共用一艘船，那么就這樣安排。否則，最重的人無法與任何人配對，那么他們將自己獨(dú)自乘一艘船。這么做的原因是，如果最輕的人可以與任何人配對，那么他們也可以與最重的人配對。

那我們首先讓她們按照體重排好隊(duì)

那我們首先看最瘦的和最胖的，連個加起來有124斤，是坐不了一條船的

那我們只能讓最胖的自己坐一條船，然后看第二胖的能不能和最瘦的一起坐船走，這時候用了一條船。

可以發(fā)現(xiàn)最瘦的果然和第二胖的人體重一共為113kg，她們是可以一起坐船走的，這時候一共占用了兩條船，接下來繼續(xù)看第二瘦和第三胖的人。

最后組隊(duì)情況為：

54kg - 59kg，55kg - 58kg，56kg - 57kg，70kg

從上我們可以看到雙指針即是在有序數(shù)組的情況下，我們通過兩個指針在遍歷的過程中進(jìn)行標(biāo)記，對滿足條件的進(jìn)行處理，直至遍歷完整個數(shù)組。

（二）快慢指針

快慢指針中的快慢即兩個指針移動的快慢不同，通過兩個指針移動速度的不同，判斷數(shù)組或鏈表的長度、是否有環(huán)、特定位置的數(shù)值等。

舉個例子：

假如有一條跑道，假如有環(huán)，會沿著環(huán)一直跑，烏龜每次走一步，兔子每次走兩步，那么如果有環(huán)，那么他們必定會相遇，過程如下：

一個跑得快，一個跑得慢。如果不含有環(huán)，跑得快的那個指針最終會遇到 null，說明鏈表不含環(huán)；如果含有環(huán)，快指針最終會超慢指針一圈，和慢指針相遇，說明鏈表含有環(huán)。