作者：labuladong

公眾號(hào)：labuladong

本文是一兩年前發(fā)過的一篇文章，當(dāng)時(shí)沒多少人看，現(xiàn)在由于賬號(hào)遷移的原因公眾號(hào)里都搜索不到了，我就重新加工了一下，并且添加了新內(nèi)容，直接套雙指針技巧秒殺 5 道算法題。

其實(shí)，鼎鼎有名的「滑動(dòng)窗口算法」就是一種雙指針技巧，我們之前的爆文我寫了套框架，把滑動(dòng)窗口算法變成了默寫題就有這么一段：

我把雙指針技巧再分為兩類，一類是「快慢指針」，一類是「左右指針」。前者解決主要解決鏈表中的問題，比如典型的判定鏈表中是否包含環(huán)；后者主要解決數(shù)組（或者字符串）中的問題，比如二分查找。

一、快慢指針的常見算法

快慢指針一般都初始化指向鏈表的頭結(jié)點(diǎn)head，前進(jìn)時(shí)快指針fast在前，慢指針slow在后，巧妙解決一些鏈表中的問題。

1、判定鏈表中是否含有環(huán)

這屬于鏈表最基本的操作了，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)應(yīng)該對(duì)這個(gè)算法思想都不陌生。

單鏈表的特點(diǎn)是每個(gè)節(jié)點(diǎn)只知道下一個(gè)節(jié)點(diǎn)，所以一個(gè)指針的話無法判斷鏈表中是否含有環(huán)的。

如果鏈表中不含環(huán)，那么這個(gè)指針最終會(huì)遇到空指針null表示鏈表到頭了，這還好說，可以判斷該鏈表不含環(huán)：

booleanhasCycle(ListNodehead){ while(head!=null) head=head.next; returnfalse; }

但是如果鏈表中含有環(huán)，那么這個(gè)指針就會(huì)陷入死循環(huán)，因?yàn)?a target="_blank">環(huán)形數(shù)組中沒有null指針作為尾部節(jié)點(diǎn)。

經(jīng)典解法就是用兩個(gè)指針，一個(gè)跑得快，一個(gè)跑得慢。如果不含有環(huán)，跑得快的那個(gè)指針最終會(huì)遇到null，說明鏈表不含環(huán)；如果含有環(huán)，快指針最終會(huì)超慢指針一圈，和慢指針相遇，說明鏈表含有環(huán)。

力扣第 141 題就是這個(gè)問題，解法代碼如下：

booleanhasCycle(ListNodehead){ ListNodefast,slow; fast=slow=head; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; if(fast==slow)returntrue; } returnfalse; }

2、已知鏈表中含有環(huán)，返回這個(gè)環(huán)的起始位置

這個(gè)問題一點(diǎn)都不困難，有點(diǎn)類似腦筋急轉(zhuǎn)彎，先直接看代碼：

ListNodedetectCycle(ListNodehead){ ListNodefast,slow; fast=slow=head; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; if(fast==slow)break; } //上面的代碼類似hasCycle函數(shù) slow=head; while(slow!=fast){ fast=fast.next; slow=slow.next; } returnslow; }

可以看到，當(dāng)快慢指針相遇時(shí)，讓其中任一個(gè)指針指向頭節(jié)點(diǎn)，然后讓它倆以相同速度前進(jìn)，再次相遇時(shí)所在的節(jié)點(diǎn)位置就是環(huán)開始的位置。這是為什么呢？

第一次相遇時(shí)，假設(shè)慢指針slow走了k步，那么快指針fast一定走了2k步：

fast一定比slow多走了k步，這多走的k步其實(shí)就是fast指針在環(huán)里轉(zhuǎn)圈圈，所以k的值就是環(huán)長(zhǎng)度的「整數(shù)倍」。

說句題外話，之前還有讀者爭(zhēng)論為什么是環(huán)長(zhǎng)度整數(shù)倍，我舉個(gè)簡(jiǎn)單的例子你就明白了，我們想一想極端情況，假設(shè)環(huán)長(zhǎng)度就是 1，如下圖：

那么fast肯定早早就進(jìn)環(huán)里轉(zhuǎn)圈圈了，而且肯定會(huì)轉(zhuǎn)好多圈，這不就是環(huán)長(zhǎng)度的整數(shù)倍嘛。

言歸正傳，設(shè)相遇點(diǎn)距環(huán)的起點(diǎn)的距離為m，那么環(huán)的起點(diǎn)距頭結(jié)點(diǎn)head的距離為k - m，也就是說如果從head前進(jìn)k - m步就能到達(dá)環(huán)起點(diǎn)。

巧的是，如果從相遇點(diǎn)繼續(xù)前進(jìn)k - m步，也恰好到達(dá)環(huán)起點(diǎn)。你甭管fast在環(huán)里到底轉(zhuǎn)了幾圈，反正走k步可以到相遇點(diǎn)，那走k - m步一定就是走到環(huán)起點(diǎn)了：

所以，只要我們把快慢指針中的任一個(gè)重新指向head，然后兩個(gè)指針同速前進(jìn)，k - m步后就會(huì)相遇，相遇之處就是環(huán)的起點(diǎn)了。

3、尋找鏈表的中點(diǎn)

類似上面的思路，我們還可以讓快指針一次前進(jìn)兩步，慢指針一次前進(jìn)一步，當(dāng)快指針到達(dá)鏈表盡頭時(shí)，慢指針就處于鏈表的中間位置。

力扣第 876 題就是找鏈表中點(diǎn)的題目，解法代碼如下：

ListNodemiddleNode(ListNodehead){ ListNodefast,slow; fast=slow=head; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; } //slow就在中間位置 returnslow; }

當(dāng)鏈表的長(zhǎng)度是奇數(shù)時(shí)，slow恰巧停在中點(diǎn)位置；如果長(zhǎng)度是偶數(shù)，slow最終的位置是中間偏右：

尋找鏈表中點(diǎn)的一個(gè)重要作用是對(duì)鏈表進(jìn)行歸并排序。

回想數(shù)組的歸并排序：求中點(diǎn)索引遞歸地把數(shù)組二分，最后合并兩個(gè)有序數(shù)組。對(duì)于鏈表，合并兩個(gè)有序鏈表是很簡(jiǎn)單的，難點(diǎn)就在于二分。

但是現(xiàn)在你學(xué)會(huì)了找到鏈表的中點(diǎn)，就能實(shí)現(xiàn)鏈表的二分了。關(guān)于歸并排序的具體內(nèi)容本文就不具體展開了。

4、尋找鏈表的倒數(shù)第n個(gè)元素

這是力扣第 19 題「刪除鏈表的倒數(shù)第n個(gè)元素」，先看下題目：

我們的思路還是使用快慢指針，讓快指針先走n步，然后快慢指針開始同速前進(jìn)。這樣當(dāng)快指針走到鏈表末尾null時(shí)，慢指針?biāo)诘奈恢镁褪堑箶?shù)第n個(gè)鏈表節(jié)點(diǎn)（n不會(huì)超過鏈表長(zhǎng)度）。

解法比較簡(jiǎn)單，直接看代碼吧：

ListNoderemoveNthFromEnd(ListNodehead,intn){ ListNodefast,slow; fast=slow=head; //快指針先前進(jìn)n步 while(n-->0){ fast=fast.next; } if(fast==null){ //如果此時(shí)快指針走到頭了， //說明倒數(shù)第n個(gè)節(jié)點(diǎn)就是第一個(gè)節(jié)點(diǎn) returnhead.next; } //讓慢指針和快指針同步向前 while(fast!=null&&fast.next!=null){ fast=fast.next; slow=slow.next; } //slow.next就是倒數(shù)第n個(gè)節(jié)點(diǎn)，刪除它 slow.next=slow.next.next; returnhead; }

二、左右指針的常用算法

左右指針在數(shù)組中實(shí)際是指兩個(gè)索引值，一般初始化為left = 0, right = nums.length - 1。

1、二分查找

前文二分查找框架詳解有詳細(xì)講解，這里只寫最簡(jiǎn)單的二分算法，旨在突出它的雙指針特性：

intbinarySearch(int[]nums,inttarget){ intleft=0; intright=nums.length-1; while(left<=?right)?{ ????????int?mid?=?(right?+?left)?/?2; ????????if(nums[mid]?==?target) ????????????return?mid;? ????????else?if?(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的大?。?/p>

int[]twoSum(int[]nums,inttarget){ intleft=0,right=nums.length-1; while(lefttarget){ right--;//讓sum小一點(diǎn) } } returnnewint[]{-1,-1}; }

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

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

voidreverseString(char[]arr){ intleft=0; intright=arr.length-1; while(left

4、滑動(dòng)窗口算法

這也許是雙指針技巧的最高境界了，如果掌握了此算法，可以解決一大類子字符串匹配的問題，不過「滑動(dòng)窗口」稍微比上述的這些算法復(fù)雜些。

不過這類算法是有框架模板的，而且前文我寫了首詩(shī)，把滑動(dòng)窗口算法變成了默寫題就講解了「滑動(dòng)窗口」算法模板，幫大家秒殺幾道子串匹配的問題，如果沒有看過，建議去看看。

責(zé)任編輯：PSY

原文標(biāo)題：雙指針技巧直接秒殺五道算法題

文章出處：【微信公眾號(hào)：算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。