1. 雙指針到底解決了什么問(wèn)題先從一個(gè)最常見(jiàn)的場(chǎng)景說(shuō)起。假設(shè)你拿到了一個(gè)有序數(shù)組要找出其中兩個(gè)數(shù)使它們的和等于某個(gè)目標(biāo)值。最直接的想法是兩層循環(huán)暴力枚舉第一層固定一個(gè)數(shù)第二層遍歷剩下的數(shù)去檢查。這個(gè)方案的復(fù)雜度是O(n2)數(shù)據(jù)量小的時(shí)候沒(méi)什么感覺(jué)一旦數(shù)組規(guī)模來(lái)到上萬(wàn)級(jí)別性能就會(huì)明顯吃力。而同樣的問(wèn)題用雙指針可以在O(n)時(shí)間內(nèi)解決差距是數(shù)量級(jí)的。我在實(shí)際刷題和寫(xiě)業(yè)務(wù)代碼時(shí)對(duì)雙指針的第一感受是它本質(zhì)上是用兩個(gè)下標(biāo)協(xié)同移動(dòng)來(lái)替代兩層循環(huán)的暴力枚舉。很多O(n2)的暴力方案之所以慢是因?yàn)樗隽舜罅繜o(wú)意義的重復(fù)掃描。而雙指針通過(guò)維護(hù)兩個(gè)指針的移動(dòng)規(guī)則把哪些組合不需要檢查直接剪掉從而把復(fù)雜度降下來(lái)。雙指針并不局限于數(shù)組。鏈表里判斷是否有環(huán)、字符串里找最長(zhǎng)無(wú)重復(fù)子串、有序數(shù)組里找兩數(shù)之和這些都繞不開(kāi)雙指針。它甚至不只是算法題里的技巧在日常業(yè)務(wù)代碼里合并兩個(gè)有序列表、過(guò)濾重復(fù)項(xiàng)、查找滿足條件的連續(xù)區(qū)間同樣可以用這套思路來(lái)優(yōu)化。這篇文章不打算講理論空殼我想直接把幾種最常用的雙指針模式拆開(kāi)來(lái)說(shuō)清楚對(duì)撞指針、快慢指針、滑動(dòng)窗口式的同向指針以及它們各自的適用前提、代碼骨架、典型例題和我實(shí)際踩過(guò)的坑。先說(shuō)一個(gè)最重要的判斷標(biāo)準(zhǔn)一道題能不能用雙指針取決于數(shù)據(jù)是否具備某種單調(diào)性或者是否可以在移動(dòng)指針的過(guò)程中保持這種單調(diào)性。舉個(gè)例子在有序數(shù)組里找兩數(shù)之和數(shù)組從左到右是遞增的。如果左指針指向的值加右指針指向的值已經(jīng)大于目標(biāo)值那么左指針再往右移動(dòng)和只會(huì)更大所以唯一合理的操作是讓右指針左移。這個(gè)能明確判斷該往哪個(gè)方向移動(dòng)的性質(zhì)就是雙指針能成立的根本原因。沒(méi)有單調(diào)性雙指針就失效了。理解了這一點(diǎn)后面所有場(chǎng)景都能往這個(gè)核心邏輯上靠。2. 對(duì)撞指針有序場(chǎng)景下的收窄查找對(duì)撞指針是雙指針里最直觀、最好理解的一種模式。兩個(gè)指針?lè)謩e從序列的兩端出發(fā)向中間移動(dòng)直到相遇。它的代碼骨架極其簡(jiǎn)單但這層簡(jiǎn)單背后藏著利用有序性剪枝的核心思想。2.1 代碼骨架與移動(dòng)邏輯def two_sum_sorted(numbers: list[int], target: int) - list[int]: left, right 0, len(numbers) - 1 while left right: current_sum numbers[left] numbers[right] if current_sum target: return [left 1, right 1] # 返回下標(biāo)按1計(jì)數(shù) elif current_sum target: left 1 else: right - 1 return [-1, -1]這段代碼的移動(dòng)邏輯是兩數(shù)之和小于目標(biāo)值時(shí)說(shuō)明需要更大的數(shù)左指針右移兩數(shù)之和大于目標(biāo)值時(shí)說(shuō)明需要更小的數(shù)右指針左移。整個(gè)過(guò)程沒(méi)有回溯每一步都基于當(dāng)前狀態(tài)做出確定性的方向選擇。為什么這個(gè)邏輯成立關(guān)鍵在于數(shù)組有序。當(dāng)前和偏小意味著左指針右邊所有元素和右指針當(dāng)前元素的組合只會(huì)更大但左指針右邊的元素已經(jīng)通過(guò)左移右指針的方式排除掉了所以唯一剩下可能湊出目標(biāo)值的方向就是左指針右移。反過(guò)來(lái)也一樣。這就是剪枝的含義——不需要檢查的組合直接被跳過(guò)。2.2 回文串判斷對(duì)撞指針的另一個(gè)高發(fā)場(chǎng)景判斷一個(gè)字符串是否為回文串是對(duì)撞指針的經(jīng)典應(yīng)用。左指針從頭部出發(fā)右指針從尾部出發(fā)兩個(gè)指針不斷向中間靠攏每一步比較兩個(gè)字符是否相等。def is_palindrome(s: str) - bool: left, right 0, len(s) - 1 while left right: if s[left] ! s[right]: return False left 1 right - 1 return True這個(gè)場(chǎng)景看似簡(jiǎn)單但有一個(gè)實(shí)際業(yè)務(wù)中很容易踩的坑如果字符串中包含空格、標(biāo)點(diǎn)符號(hào)并忽略大小寫(xiě)那就不應(yīng)該直接比較字符而應(yīng)該先做預(yù)處理或跳過(guò)非字母數(shù)字字符。很多新手在LeetCode上做這個(gè)題的時(shí)候直接把原始字符串拿來(lái)比較結(jié)果在邊界用例上報(bào)錯(cuò)。def is_palindrome_with_filter(s: str) - bool: left, right 0, len(s) - 1 while left right: while left right and not s[left].isalnum(): left 1 while left right and not s[right].isalnum(): right - 1 if s[left].lower() ! s[right].lower(): return False left 1 right - 1 return True這里有一個(gè)細(xì)節(jié)值得注意內(nèi)部while循環(huán)一定要加上left right這個(gè)條件否則指針可能越界。我自己就犯過(guò)這個(gè)錯(cuò)誤——字符串全部是非字母字符時(shí)左指針一路往右走直接沖出數(shù)組邊界。2.3 盛最多水的容器不需要有序也能用對(duì)撞指針很多人以為對(duì)撞指針只適用于有序數(shù)組實(shí)際上這是一個(gè)誤解。有一道很經(jīng)典的題目——盛最多水的容器給定一組高度值選擇兩個(gè)位置構(gòu)成容器問(wèn)最多能裝多少水。這個(gè)題沒(méi)有排序數(shù)組是任意的但依然可以用對(duì)撞指針。核心邏輯是容器的容量由較矮的那塊板決定如果移動(dòng)較高的一側(cè)容量只會(huì)減少或不變所以每次都只移動(dòng)較矮的那一側(cè)。def max_area(height: list[int]) - int: left, right 0, len(height) - 1 max_water 0 while left right: current_area min(height[left], height[right]) * (right - left) max_water max(max_water, current_area) if height[left] height[right]: left 1 else: right - 1 return max_water這里單調(diào)性體現(xiàn)在短板效應(yīng)上兩個(gè)邊界之間的容量由較短邊決定。如果保留短邊、移動(dòng)長(zhǎng)邊新的容量不可能超過(guò)當(dāng)前值因?yàn)楦叨缺欢踢呄拗贫鴮挾仍诳s小。這個(gè)規(guī)律使得哪邊短就移動(dòng)哪邊成為一個(gè)確定性規(guī)則。所以對(duì)撞指針真正需要的不是整個(gè)數(shù)組有序而是存在一個(gè)可以確定性的方向選擇規(guī)則。這個(gè)結(jié)論很重要能幫你跳出雙指針只能用于有序數(shù)組的思維定式。3. 快慢指針鏈表與數(shù)組中的狀態(tài)檢測(cè)快慢指針與對(duì)撞指針最大的不同在于兩個(gè)指針的起點(diǎn)相同方向相同但速度不同。常見(jiàn)組合是一快一慢快的每次走兩步慢的每次走一步。這種模式在鏈表問(wèn)題里尤其常見(jiàn)但也適用于數(shù)組。3.1 環(huán)形鏈表檢測(cè)Floyd判圈算法的Python實(shí)現(xiàn)判斷一個(gè)鏈表是否成環(huán)最經(jīng)典的解法就是快慢指針。想象兩個(gè)人繞操場(chǎng)跑步速度快的人遲早會(huì)追上速度慢的人——如果賽道是一個(gè)環(huán)的話。如果賽道是直的快的人只會(huì)率先到達(dá)終點(diǎn)。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def has_cycle(head: ListNode) - bool: slow, fast head, head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return False這里要注意while循環(huán)的終止條件fast and fast.next兩個(gè)都不能為空。因?yàn)閒ast每次走兩步如果fast本身為空或者fast.next為空就說(shuō)明鏈表走到了盡頭不可能有環(huán)。少了這個(gè)條件代碼會(huì)在訪問(wèn)fast.next.next時(shí)拋空指針異常。進(jìn)一步問(wèn)如果鏈表中存在環(huán)如何找到環(huán)的入口這需要一點(diǎn)數(shù)學(xué)推導(dǎo)。設(shè)頭節(jié)點(diǎn)到環(huán)入口的距離為a環(huán)入口到相遇點(diǎn)的距離為b環(huán)的周長(zhǎng)為c。slow走的路程是abfast走的路程是abkck為fast在環(huán)內(nèi)多走的圈數(shù)。由于fast的速度是slow的兩倍所以2(ab) abkc ab kc a kc - b (k-1)c (c-b)這意味著從相遇點(diǎn)繼續(xù)往前走(c-b)步加上(k-1)圈就能到達(dá)環(huán)入口而從頭節(jié)點(diǎn)走a步也能到達(dá)環(huán)入口。所以相遇之后把一個(gè)指針移回head兩個(gè)指針都以一次一格的步速同步前進(jìn)再次相遇的位置就是環(huán)入口。def detect_cycle_entry(head: ListNode) - ListNode: slow, fast head, head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: break else: return None slow head while slow is not fast: slow slow.next fast fast.next return slow這段代碼的for...else實(shí)際上是while...else結(jié)構(gòu)在Python里很實(shí)用循環(huán)正常結(jié)束未break時(shí)執(zhí)行else分支返回None。手寫(xiě)鏈表題的時(shí)候這個(gè)寫(xiě)法可以少寫(xiě)一個(gè)標(biāo)志位。3.2 數(shù)組中的快慢指針原地去重快慢指針在數(shù)組里最常見(jiàn)的應(yīng)用是原地去重。給定一個(gè)有序數(shù)組要求原地刪除重復(fù)元素返回去重后的長(zhǎng)度。慢指針指向已去重區(qū)間的末尾快指針用于遍歷整個(gè)數(shù)組。def remove_duplicates(nums: list[int]) - int: if not nums: return 0 slow 0 for fast in range(1, len(nums)): if nums[fast] ! nums[slow]: slow 1 nums[slow] nums[fast] return slow 1這里慢指針維護(hù)的是新數(shù)組的寫(xiě)入位置快指針負(fù)責(zé)掃描原數(shù)組。每當(dāng)快指針遇到一個(gè)新值就把它寫(xiě)到慢指針的下一個(gè)位置。整個(gè)過(guò)程利用了數(shù)組有序這個(gè)前提——重復(fù)元素一定相鄰所以只需要比較相鄰位置的值不需要額外空間時(shí)間復(fù)雜度O(n)。我在實(shí)際做這類題的時(shí)候有一個(gè)心得快慢指針在數(shù)組中的應(yīng)用本質(zhì)上是一種讀寫(xiě)分離?？熘羔権?fù)責(zé)讀慢指針負(fù)責(zé)寫(xiě)。讀得快、寫(xiě)得慢中間被覆蓋的區(qū)域就是已經(jīng)不需要的舊值。這個(gè)視角一旦建立很多變種題比如把特定元素移動(dòng)到數(shù)組末尾、移除指定元素都能用同一套模板快速寫(xiě)出來(lái)。3.3 找鏈表的中間節(jié)點(diǎn)另一個(gè)快慢指針的典型應(yīng)用是找鏈表的中間節(jié)點(diǎn)?？熘羔樀浇K點(diǎn)時(shí)慢指針剛好在一半的位置。def middle_node(head: ListNode) - ListNode: slow fast head while fast and fast.next: slow slow.next fast fast.next.next return slow這個(gè)技巧的實(shí)際價(jià)值不只是找中間點(diǎn)它還是很多更復(fù)雜問(wèn)題的基礎(chǔ)步驟。比如判斷一個(gè)鏈表是否為回文鏈表標(biāo)準(zhǔn)解法就是先找中點(diǎn)再反轉(zhuǎn)后半段最后兩邊同步比較。整個(gè)流程里快慢指針找中點(diǎn)是第一步如果沒(méi)有這個(gè)技巧你就只能先遍歷一遍統(tǒng)計(jì)長(zhǎng)度再用計(jì)數(shù)器走一半代碼會(huì)啰嗦不少。4. 滑動(dòng)窗口雙指針中最容易被低估的變體滑動(dòng)窗口可以理解為同向雙指針的進(jìn)階版兩個(gè)指針都從左往右移動(dòng)且始終保持left right。右指針負(fù)責(zé)擴(kuò)展窗口左指針負(fù)責(zé)收縮窗口整個(gè)窗口像一條毛毛蟲(chóng)一樣在序列上爬行。很多人在學(xué)習(xí)雙指針的時(shí)候會(huì)把滑動(dòng)窗口當(dāng)作另一個(gè)獨(dú)立的知識(shí)點(diǎn)其實(shí)它底層就是雙指針。理解這一點(diǎn)很重要——一旦你接受了滑動(dòng)窗口是雙指針的一種你就不需要額外記憶一套新的模板只需要記住同一個(gè)骨架的不同變體。4.1 無(wú)重復(fù)字符的最長(zhǎng)子串題目給定一個(gè)字符串找出其中不含有重復(fù)字符的最長(zhǎng)子串的長(zhǎng)度。這是滑動(dòng)窗口最經(jīng)典的入門(mén)題。def length_of_longest_substring(s: str) - int: window set() left 0 max_len 0 for right in range(len(s)): while s[right] in window: window.remove(s[left]) left 1 window.add(s[right]) max_len max(max_len, right - left 1) return max_len核心邏輯右指針每次擴(kuò)展一個(gè)字符如果這個(gè)字符已經(jīng)在窗口里就不斷收縮左指針直到把重復(fù)字符移出窗口。窗口內(nèi)的字符始終用一個(gè)set來(lái)維護(hù)判斷重復(fù)的復(fù)雜度是O(1)。這個(gè)題的坑點(diǎn)在于什么時(shí)候更新答案。正確做法是在把新字符加入窗口之后更新因?yàn)榇丝痰拇翱诓攀呛戏ǖ臒o(wú)重復(fù)窗口。如果你在while循環(huán)之前就更新答案會(huì)把包含重復(fù)字符的子串長(zhǎng)度也算進(jìn)去導(dǎo)致結(jié)果偏大。這個(gè)順序問(wèn)題不親自跑一遍永遠(yuǎn)記不住。4.2 最小覆蓋子串窗口內(nèi)字符計(jì)數(shù)的精細(xì)化比無(wú)重復(fù)子串進(jìn)階一些的是最小覆蓋子串問(wèn)題給定一個(gè)源字符串s和一個(gè)目標(biāo)字符串t在s中找到包含t所有字符的最短子串。這個(gè)題的難點(diǎn)在于t中的字符可能有重復(fù)所以不能用set需要dict來(lái)記錄每個(gè)字符的需求量。from collections import Counter def min_window(s: str, t: str) - str: if not s or not t: return need Counter(t) window {} formed 0 required len(need) left 0 ans float(inf), None, None for right in range(len(s)): c s[right] window[c] window.get(c, 0) 1 if c in need and window[c] need[c]: formed 1 while left right and formed required: if right - left 1 ans[0]: ans (right - left 1, left, right) d s[left] window[d] - 1 if d in need and window[d] need[d]: formed - 1 left 1 return s[ans[1]:ans[2] 1] if ans[0] ! float(inf) else 這里的formed變量記錄已經(jīng)滿足需求的字符種類數(shù)。只有當(dāng)某個(gè)字符在窗口中的數(shù)量恰好等于需求數(shù)量時(shí)formed才加一收縮窗口后如果數(shù)量不足formed再減一。這個(gè)題的復(fù)雜程度主要來(lái)自狀態(tài)維護(hù)但骨架依然是滑動(dòng)窗口的標(biāo)準(zhǔn)結(jié)構(gòu)。我總結(jié)了幾個(gè)關(guān)鍵點(diǎn)required代表t中不同字符的個(gè)數(shù)不是t的總長(zhǎng)度判斷條件用window[c] need[c]而不是因?yàn)橐坏┏^(guò)formed不會(huì)重復(fù)增加收縮窗口時(shí)window[d] - 1不能省否則狀態(tài)會(huì)越走越偏4.3 什么時(shí)候用滑動(dòng)窗口而不是我的直覺(jué)方案遇到最長(zhǎng)子串最短子串滿足某條件的連續(xù)區(qū)間這類問(wèn)題時(shí)先想到滑動(dòng)窗口就對(duì)了。這種問(wèn)題的共性特征是子數(shù)組或子串是連續(xù)的且存在一個(gè)隨著窗口擴(kuò)大逐漸變好、隨著窗口收縮逐漸變差的單調(diào)關(guān)系。比如無(wú)重復(fù)字符的最長(zhǎng)子串窗口擴(kuò)大可能引入重復(fù)字符變差收縮可以恢復(fù)合法性變好。這種擴(kuò)大變差、收縮變好的性質(zhì)就是滑動(dòng)窗口可以使用的信號(hào)。如果題目要求的是不連續(xù)的子序列滑動(dòng)窗口就派不上用場(chǎng)那是動(dòng)態(tài)規(guī)劃或回溯的領(lǐng)地。獨(dú)立判斷這個(gè)信號(hào)比背模板重要得多。模板背多了會(huì)發(fā)現(xiàn)at the end每個(gè)雙指針題都長(zhǎng)得差不多但判斷能不能用才是面試和實(shí)戰(zhàn)里真正的分水嶺。5. 雙指針的邊界條件與常見(jiàn)錯(cuò)誤復(fù)盤(pán)雙指針代碼寫(xiě)起來(lái)不難難的是把邊界條件一次寫(xiě)對(duì)。下面這些坑都是我在實(shí)際編碼里踩過(guò)或者看別人踩過(guò)的。5.1 循環(huán)條件到底是left right還是left right對(duì)撞指針的循環(huán)條件多數(shù)情況下用left right。因?yàn)樵趦蓚€(gè)數(shù)相加這個(gè)場(chǎng)景里left和right指向同一個(gè)元素沒(méi)有意義——一個(gè)元素不能用兩次。但在回文串判斷里如果字符串長(zhǎng)度為奇數(shù)中間那個(gè)字符和自身比較天然相等所以left right就足夠覆蓋了。如果用left right在偶數(shù)長(zhǎng)度回文串的最后一輪會(huì)導(dǎo)致left越界?？炻羔樥抑悬c(diǎn)時(shí)循環(huán)條件是while fast and fast.next這和數(shù)組對(duì)撞的left right在形式上完全不同一定要區(qū)分記憶。5.2 指針移動(dòng)后狀態(tài)沒(méi)有同步更新這是滑動(dòng)窗口最容易出錯(cuò)的地方。比如在最小覆蓋子串里你收縮左指針后必須同步更新window字典里對(duì)應(yīng)字符的計(jì)數(shù)還要檢查formed是否需要減一。很多人在筆試時(shí)把formed的判斷邏輯寫(xiě)在收縮窗口之外結(jié)果窗口已經(jīng)非法了狀態(tài)卻還停留在合法狀態(tài)導(dǎo)致答案錯(cuò)誤。這類問(wèn)題的調(diào)試很痛苦因?yàn)檎w跑了看不出問(wèn)題只有跑到特定輸入才會(huì)錯(cuò)。我的建議是每次移動(dòng)指針之后立刻檢查所有和這個(gè)位置綁定的狀態(tài)變量是否同步更新。寫(xiě)代碼的時(shí)候不要先寫(xiě)移動(dòng)邏輯再補(bǔ)狀態(tài)更新而是先把移動(dòng)指針會(huì)導(dǎo)致哪些狀態(tài)變化列出來(lái)再動(dòng)筆寫(xiě)。5.3 數(shù)組越界與鏈表空指針對(duì)撞指針中內(nèi)部while循環(huán)缺少left right條件會(huì)越界?？炻羔樦衒ast.next可能為None。鏈表題中空鏈表的head為None。這些都是空指針異常的高發(fā)點(diǎn)。實(shí)踐中我傾向于在寫(xiě)代碼之前先把極端輸入列在注釋里空數(shù)組、單元素?cái)?shù)組、全重復(fù)數(shù)組、全不重復(fù)數(shù)組、空字符串、單字符字符串、無(wú)環(huán)鏈表、只有頭節(jié)點(diǎn)的鏈表。把這些case都跑通了雙指針代碼基本就不會(huì)有邊界問(wèn)題。6. 如何判斷一道題該不該上雙指針我的實(shí)戰(zhàn)決策路徑最后分享一套我自己的判斷路徑。拿到一道算法題我先看數(shù)據(jù)結(jié)構(gòu)的類型和問(wèn)題的形狀再?zèng)Q定要不要用雙指針。第一步看數(shù)據(jù)是否連續(xù)。數(shù)組、字符串、鏈表這類線性結(jié)構(gòu)天然適合指針操作樹(shù)和圖一般不適合雙指針因?yàn)槁窂讲皇蔷€性的。第二步看題目是否要求O(n)或O(nlog n)的時(shí)間復(fù)雜度。如果暴力解O(n2)是可以接受的雙指針帶來(lái)的收益就不明顯但大多數(shù)LeetCode中等的題目暴力解都會(huì)被卡時(shí)間這時(shí)候雙指針就是性價(jià)比最高的解法之一。第三步看是否存在單調(diào)性或者固定的移動(dòng)規(guī)則。有序數(shù)組找兩數(shù)之和有單調(diào)性盛最多水的容器有移動(dòng)矮邊的確定性環(huán)形鏈表有快慢必相遇的邏輯。任何一個(gè)成立都可以放心用雙指針。第四步看能不能通過(guò)排序建立單調(diào)性。比如三數(shù)之和本身數(shù)組無(wú)序但先排序就可以用對(duì)撞指針來(lái)優(yōu)化兩數(shù)之和部分。排序的時(shí)間復(fù)雜度O(nlog n)比整體O(n2)的暴力方案仍然快不少。把這幾步走完就能避免拿雙指針硬套所有題的尷尬。雙指針不是銀彈它適合的題目都有同樣清晰的信號(hào)。我現(xiàn)在處理算法相關(guān)的問(wèn)題都是先用雙指針篩一遍不行再上前綴和、二分、堆這些更重的工具。這種由輕到重的決策順序幫我省下了大量調(diào)試時(shí)間。希望這套思路對(duì)你也同樣有用。