雙指針技巧在處理數(shù)組和鏈表相關(guān)問題時(shí)經(jīng)常用到，主要分為兩類：左右指針和快慢指針。

所謂左右指針，就是兩個(gè)指針相向而行或者相背而行；而所謂快慢指針，就是兩個(gè)指針同向而行，一快一慢。

對(duì)于單鏈表來說，大部分技巧都屬于快慢指針，前文 單鏈表的六大解題套路 都涵蓋了，比如鏈表環(huán)判斷，倒數(shù)第K個(gè)鏈表節(jié)點(diǎn)等問題，它們都是通過一個(gè)fast快指針和一個(gè)slow慢指針配合完成任務(wù)。

在數(shù)組中并沒有真正意義上的指針，但我們可以把索引當(dāng)做數(shù)組中的指針，這樣也可以在數(shù)組中施展雙指針技巧，本文主要講數(shù)組相關(guān)的雙指針算法。

一、快慢指針技巧

數(shù)組問題中比較常見且難度不高的的快慢指針技巧，是讓你原地修改數(shù)組。

比如說看下力扣第 26 題「刪除有序數(shù)組中的重復(fù)項(xiàng)」，讓你在有序數(shù)組去重：

函數(shù)簽名如下：

intremoveDuplicates(int[]nums);

簡(jiǎn)單解釋一下什么是原地修改：

如果不是原地修改的話，我們直接 new 一個(gè)int[]數(shù)組，把去重之后的元素放進(jìn)這個(gè)新數(shù)組中，然后返回這個(gè)新數(shù)組即可。

但是現(xiàn)在題目讓你原地刪除，不允許 new 新數(shù)組，只能在原數(shù)組上操作，然后返回一個(gè)長(zhǎng)度，這樣就可以通過返回的長(zhǎng)度和原始數(shù)組得到我們?nèi)ブ睾蟮脑赜心男┝恕?/span>

由于數(shù)組已經(jīng)排序，所以重復(fù)的元素一定連在一起，找出它們并不難。但如果毎找到一個(gè)重復(fù)元素就立即原地刪除它，由于數(shù)組中刪除元素涉及數(shù)據(jù)搬移，整個(gè)時(shí)間復(fù)雜度是會(huì)達(dá)到O(N^2)。

高效解決這道題就要用到快慢指針技巧：

我們讓慢指針slow走在后面，快指針fast走在前面探路，找到一個(gè)不重復(fù)的元素就賦值給slow并讓slow前進(jìn)一步。

這樣，就保證了nums[0..slow]都是無重復(fù)的元素，當(dāng)fast指針遍歷完整個(gè)數(shù)組nums后，nums[0..slow]就是整個(gè)數(shù)組去重之后的結(jié)果。

看代碼：

intremoveDuplicates(int[]nums){
if(nums.length==0){
return0;
}
intslow=0,fast=0;
while(fastif(nums[fast]!=nums[slow]){
slow++;
//維護(hù)nums[0..slow]無重復(fù)
nums[slow]=nums[fast];
}
fast++;
}
//數(shù)組長(zhǎng)度為索引+1
returnslow+1;
}

算法執(zhí)行的過程如下 GIF 圖：

再簡(jiǎn)單擴(kuò)展一下，看看力扣第 83 題「刪除排序鏈表中的重復(fù)元素」，如果給你一個(gè)有序的單鏈表，如何去重呢？

其實(shí)和數(shù)組去重是一模一樣的，唯一的區(qū)別是把數(shù)組賦值操作變成操作指針而已，你對(duì)照著之前的代碼來看：

ListNodedeleteDuplicates(ListNodehead){
if(head==null)returnnull;
ListNodeslow=head,fast=head;
while(fast!=null){
if(fast.val!=slow.val){
//nums[slow]=nums[fast];
slow.next=fast;
//slow++;
slow=slow.next;
}
//fast++
fast=fast.next;
}
//斷開與后面重復(fù)元素的連接
slow.next=null;
returnhead;
}

算法執(zhí)行的過程請(qǐng)看下面這個(gè) GIF：

這里可能有讀者會(huì)問，鏈表中那些重復(fù)的元素并沒有被刪掉，就讓這些節(jié)點(diǎn)在鏈表上掛著，合適嗎？

這就要探討不同語言的特性了，像 Java/Python 這類帶有垃圾回收的語言，可以幫我們自動(dòng)找到并回收這些「懸空」的鏈表節(jié)點(diǎn)的內(nèi)存，而像 C++ 這類語言沒有自動(dòng)垃圾回收的機(jī)制，確實(shí)需要我們編寫代碼時(shí)手動(dòng)釋放掉這些節(jié)點(diǎn)的內(nèi)存。

不過話說回來，就算法思維的培養(yǎng)來說，我們只需要知道這種快慢指針技巧即可。

除了讓你在有序數(shù)組/鏈表中去重，題目還可能讓你對(duì)數(shù)組中的某些元素進(jìn)行「原地刪除」。

比如力扣第 27 題「移除元素」，看下題目：

函數(shù)簽名如下：

intremoveElement(int[]nums,intval);

題目要求我們把nums中所有值為val的元素原地刪除，依然需要使用快慢指針技巧：

如果fast遇到值為val的元素，則直接跳過，否則就賦值給slow指針，并讓slow前進(jìn)一步。

這和前面說到的數(shù)組去重問題解法思路是完全一樣的，就不畫 GIF 了，直接看代碼：

intremoveElement(int[]nums,intval){
intfast=0,slow=0;
while(fastif(nums[fast]!=val){
nums[slow]=nums[fast];
slow++;
}
fast++;
}
returnslow;
}

注意這里和有序數(shù)組去重的解法有一個(gè)細(xì)節(jié)差異，我們這里是先給nums[slow]賦值然后再給slow++，這樣可以保證nums[0..slow-1]是不包含值為val的元素的，最后的結(jié)果數(shù)組長(zhǎng)度就是slow。

實(shí)現(xiàn)了這個(gè)removeElement函數(shù)，接下來看看力扣第 283 題「移動(dòng)零」：

給你輸入一個(gè)數(shù)組nums，請(qǐng)你原地修改，將數(shù)組中的所有值為 0 的元素移到數(shù)組末尾，函數(shù)簽名如下：

voidmoveZeroes(int[]nums);

比如說給你輸入nums = [0,1,4,0,2]，你的算法沒有返回值，但是會(huì)把nums數(shù)組原地修改成[1,4,2,0,0]。

結(jié)合之前說到的幾個(gè)題目，你是否有已經(jīng)有了答案呢？

題目讓我們將所有 0 移到最后，其實(shí)就相當(dāng)于移除nums中的所有 0，然后再把后面的元素都賦值為 0 即可。

所以我們可以復(fù)用上一題的removeElement函數(shù)：

voidmoveZeroes(int[]nums){
//去除nums中的所有0，返回不含0的數(shù)組長(zhǎng)度
intp=removeElement(nums,0);
//將nums[p..]的元素賦值為0
for(;p0;
}
}

//見上文代碼實(shí)現(xiàn)
intremoveElement(int[]nums,intval);

到這里，原地修改數(shù)組的這些題目就已經(jīng)差不多了。數(shù)組中另一大類快慢指針的題目就是「滑動(dòng)窗口算法」。

我在另一篇文章 滑動(dòng)窗口算法核心框架詳解 給出了滑動(dòng)窗口的代碼框架：

/*滑動(dòng)窗口算法框架*/
voidslidingWindow(strings,stringt){
unordered_map<char,int>need,window;
for(charc:t)need[c]++;

intleft=0,right=0;
intvalid=0;
while(rightcharc=s[right];
//右移（增大）窗口
right++;
//進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新

while(windowneedsshrink){
chard=s[left];
//左移（縮小）窗口
left++;
//進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
}
}
}

具體的題目本文就不重復(fù)了，這里只強(qiáng)調(diào)滑動(dòng)窗口算法的快慢指針特性：

left指針在后，right指針在前，兩個(gè)指針中間的部分就是「窗口」，算法通過擴(kuò)大和縮小「窗口」來解決某些問題。

二、左右指針的常用算法

1、二分查找

我在另一篇文章 二分查找框架詳解 中有詳細(xì)探討二分搜索代碼的細(xì)節(jié)問題，這里只寫最簡(jiǎn)單的二分算法，旨在突出它的雙指針特性：

intbinarySearch(int[]nums,inttarget){
//一左一右兩個(gè)指針相向而行
intleft=0,right=nums.length-1;
while(left<=?right)?{
????????intmid=(right+left)/2;
if(nums[mid]==target)
returnmid;
elseif(nums[mid]1;
elseif(nums[mid]>target)
right=mid-1;
}
return-1;
}

2、兩數(shù)之和

看下力扣第 167 題「兩數(shù)之和 II」：

只要數(shù)組有序，就應(yīng)該想到雙指針技巧。這道題的解法有點(diǎn)類似二分查找，通過調(diào)節(jié)left和right就可以調(diào)整sum的大?。?/span>

int[]twoSum(int[]nums,inttarget){
//一左一右兩個(gè)指針相向而行
intleft=0,right=nums.length-1;
while(leftintsum=nums[left]+nums[right];
if(sum==target){
//題目要求的索引是從1開始的
returnnewint[]{left+1,right+1};
}elseif(sum//讓sum大一點(diǎn)
}elseif(sum>target){
right--;//讓sum小一點(diǎn)
}
}
returnnewint[]{-1,-1};
}

我在另一篇文章 一個(gè)函數(shù)秒殺所有 nSum 問題 中也運(yùn)用類似的左右指針技巧給出了nSum問題的一種通用思路，這里就不做贅述了。

3、反轉(zhuǎn)數(shù)組

一般編程語言都會(huì)提供reverse函數(shù)，其實(shí)這個(gè)函數(shù)的原理非常簡(jiǎn)單，力扣第 344 題「反轉(zhuǎn)字符串」就是類似的需求，讓你反轉(zhuǎn)一個(gè)char[]類型的字符數(shù)組，我們直接看代碼吧：

voidreverseString(char[]s){
//一左一右兩個(gè)指針相向而行
intleft=0,right=s.length-1;
while(left//交換s[left]和s[right]
chartemp=s[left];
s[left]=s[right];
s[right]=temp;
left++;
right--;
}
}

4、回文串判斷

首先明確一下，回文串就是正著讀和反著讀都一樣的字符串。

比如說字符串aba和abba都是回文串，因?yàn)樗鼈儗?duì)稱，反過來還是和本身一樣；反之，字符串abac就不是回文串。

現(xiàn)在你應(yīng)該能感覺到回文串問題和左右指針肯定有密切的聯(lián)系，比如讓你判斷一個(gè)字符串是不是回文串，你可以寫出下面這段代碼：

booleanisPalindrome(Strings){
//一左一右兩個(gè)指針相向而行
intleft=0,right=s.length()-1;
while(leftif(s.charAt(left)!=s.charAt(right)){
returnfalse;
}
left++;
right--;
}
returntrue;
}

那接下來我提升一點(diǎn)難度，給你一個(gè)字符串，讓你用雙指針技巧從中找出最長(zhǎng)的回文串，你會(huì)做嗎？

這就是力扣第 5 題「最長(zhǎng)回文子串」：

函數(shù)簽名如下：

StringlongestPalindrome(Strings);

找回文串的難點(diǎn)在于，回文串的的長(zhǎng)度可能是奇數(shù)也可能是偶數(shù)，解決該問題的核心是從中心向兩端擴(kuò)散的雙指針技巧。

如果回文串的長(zhǎng)度為奇數(shù)，則它有一個(gè)中心字符；如果回文串的長(zhǎng)度為偶數(shù)，則可以認(rèn)為它有兩個(gè)中心字符。所以我們可以先實(shí)現(xiàn)這樣一個(gè)函數(shù)：

//在s中尋找以s[l]和s[r]為中心的最長(zhǎng)回文串
Stringpalindrome(Strings,intl,intr){
//防止索引越界
while(l>=0&&r//雙指針，向兩邊展開
l--;r++;
}
//返回以s[l]和s[r]為中心的最長(zhǎng)回文串
returns.substring(l+1,r);
}

這樣，如果輸入相同的l和r，就相當(dāng)于尋找長(zhǎng)度為奇數(shù)的回文串，如果輸入相鄰的l和r，則相當(dāng)于尋找長(zhǎng)度為偶數(shù)的回文串。

那么回到最長(zhǎng)回文串的問題，解法的大致思路就是：

for0<=?i?1]為中心的回文串
更新答案

翻譯成代碼，就可以解決最長(zhǎng)回文子串這個(gè)問題：

StringlongestPalindrome(Strings){
Stringres="";
for(inti=0;i//以s[i]為中心的最長(zhǎng)回文子串
Strings1=palindrome(s,i,i);
//以s[i]和s[i+1]為中心的最長(zhǎng)回文子串
Strings2=palindrome(s,i,i+1);
//res=longest(res,s1,s2)
res=res.length()>s1.length()?res:s1;
res=res.length()>s2.length()?res:s2;
}
returnres;
}

你應(yīng)該能發(fā)現(xiàn)最長(zhǎng)回文子串使用的左右指針和之前題目的左右指針有一些不同：之前的左右指針都是從兩端向中間相向而行，而回文子串問題則是讓左右指針從中心向兩端擴(kuò)展。

不過這種情況也就回文串這類問題會(huì)遇到，所以我也把它歸為左右指針了。

到這里，數(shù)組相關(guān)的雙指針技巧就全部講完了，希望大家以后遇到類似的算法問題時(shí)能夠活學(xué)活用，舉一反三。

審核編輯 ：李倩