一個(gè)算法技巧，把O(n2)干成O(n)

面試官最愛(ài)考的數(shù)組題，90%的人第一反應(yīng)是嵌套循環(huán)。但有人用兩行代碼就把時(shí)間復(fù)雜度砍了一半——這不是魔法，是雙指針（Two Pointers）。

一張圖看懂核心套路

雙指針的本質(zhì)很簡(jiǎn)單：不用一個(gè)索引遍歷，而是用兩個(gè)。

它們從數(shù)組兩端出發(fā)，或者一快一慢前進(jìn)。每次移動(dòng)都基于當(dāng)前狀態(tài)做"聰明決策"，跳過(guò)大量無(wú)效計(jì)算。

原文給了三個(gè)經(jīng)典場(chǎng)景，我們逐層拆解。

場(chǎng)景一：有序數(shù)組找兩數(shù)之和

傳統(tǒng)思路：兩層循環(huán)，窮舉所有組合。時(shí)間復(fù)雜度O(n2)。

雙指針解法：

左指針從頭，右指針從尾。兩數(shù)相加，和太小則左移，和太大則右移。

代碼只有8行。因?yàn)閿?shù)組有序，每次移動(dòng)都能確定排除掉一批不可能的組合。

最壞情況？?jī)蓚€(gè)指針相遇，遍歷一遍。O(n)。

場(chǎng)景二：原地去重

這題更隱蔽。快慢指針：readIndex（讀指針）掃描新元素，writeIndex（寫(xiě)指針）只在發(fā)現(xiàn)新值時(shí)才移動(dòng)。

數(shù)組被復(fù)用為結(jié)果容器，空間復(fù)雜度O(1)。

關(guān)鍵洞察：有序數(shù)組中，重復(fù)元素一定相鄰。不需要哈希表，指針比較就夠了。

場(chǎng)景三：盛最多水的容器

LeetCode經(jīng)典題。面積 = 底 × 高，底是左右距離，高是兩板中的矮板。

雙指針從兩端收縮。哪邊矮，哪邊往中間走——因?yàn)橐苿?dòng)高的那邊，底變小、高不變，面積只會(huì)更小。

每次移動(dòng)都基于"當(dāng)前短板"做決策，全局最優(yōu)在局部比較中自然浮現(xiàn)。

為什么它能這么快？

嵌套循環(huán)的問(wèn)題是"暴力"：檢查所有可能性，不管有沒(méi)有意義。

雙指針的狡猾在于利用數(shù)組的隱藏結(jié)構(gòu)——有序性、單調(diào)性、對(duì)稱性。用一次比較的信息量，剪掉一大片搜索空間。

不是算法變快了，是干的活變少了。

你的代碼庫(kù)該更新什么

三個(gè)模板覆蓋80%面試場(chǎng)景：

? 對(duì)撞指針（兩端向中間）：有序數(shù)組求和、判斷回文、三數(shù)之和

? 快慢指針（同向不同速）：去重、判環(huán)、找中點(diǎn)

? 滑動(dòng)窗口（動(dòng)態(tài)邊界）：子串問(wèn)題、長(zhǎng)度可變區(qū)間

原文只演示了前兩種，但核心思想一致：用空間換時(shí)間太老套了，用信息換時(shí)間才是新思路。

數(shù)據(jù)收束

三個(gè)例子，時(shí)間復(fù)雜度統(tǒng)一從O(n2)降到O(n)。空間復(fù)雜度全是O(1)。

代碼行數(shù)？twoSumSorted 8行，removeDuplicates 7行，maxArea 9行。

下次寫(xiě)嵌套循環(huán)前，先問(wèn)自己一句：這數(shù)組有沒(méi)有我沒(méi)利用的結(jié)構(gòu)？