雙指針技巧在處理數(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é)活用,舉一反三。
--- EOF ---
審核編輯 :李倩
-
算法
+關(guān)注
關(guān)注
23文章
4577瀏覽量
92349 -
python
+關(guān)注
關(guān)注
54文章
4759瀏覽量
84294 -
數(shù)組
+關(guān)注
關(guān)注
1文章
412瀏覽量
25858
原文標(biāo)題:數(shù)組雙指針直接秒殺七道題目
文章出處:【微信號(hào):TheAlgorithm,微信公眾號(hào):算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
評(píng)論