三數(shù)之和與四數(shù)之和：雙指針如何砍掉兩個數(shù)量級

2026-05-19 01:55:00　來源: 閃存獵手

北京舉報

分享至

刷題時最怕遇到什么？不是遞歸，不是動態(tài)規(guī)劃，是那種看起來暴力就能解、但一提交就超時的大數(shù)組問題。三數(shù)之和與四數(shù)之和就是典型代表。暴力解法分別要到 O(n3) 和 O(n?)，數(shù)據(jù)量稍大就扛不住。但換個思路，用排序加雙指針，復(fù)雜度直接掉到 O(n2) 和 O(n3)。這篇把核心邏輯拆清楚，看完能直接上手寫代碼。

先說三數(shù)之和。題目要求找出數(shù)組中所有和為零的不重復(fù)三元組。輸入 [-1, 0, 1, 2, -1, -4]，輸出應(yīng)該是 [-1, -1, 2] 和 [-1, 0, 1] 這兩組。暴力做法是三層循環(huán)枚舉所有組合，O(n3) 的復(fù)雜度，n 超過 1000 就明顯吃力。

優(yōu)化從排序開始。數(shù)組排好序后，固定一個數(shù)，剩下就變成"找兩個數(shù)湊出某個目標(biāo)和"的經(jīng)典問題。比如固定了 -1，就需要找兩個數(shù)加起來等于 1。這時候雙指針登場：一個放在固定位置的右邊，一個放在數(shù)組末尾。和小了，左指針右移讓總和變大；和大了，右指針左移讓總和變小。找到匹配的就記錄，然后兩邊都跳過重復(fù)值繼續(xù)。

為什么排序后雙指針有效？因?yàn)橛行驍?shù)組里，左移指針一定減小當(dāng)前和，右移指針一定增大當(dāng)前和。這個單調(diào)性保證了不會漏解，也避免了無意義的遍歷。整個過程中，外層循環(huán)固定 n 個數(shù)，內(nèi)層雙指針最多走 n 步，總復(fù)雜度 O(n2)。去重也簡單：固定元素時跳過重復(fù)的，找到解后兩個指針各自跳過重復(fù)值即可。

四數(shù)之和的邏輯幾乎一樣，只是多固定一層。先排序，然后外層兩個嵌套循環(huán)固定前兩個數(shù)，剩下兩個數(shù)用雙指針找。比如數(shù)組 [1, 0, -1, 0, -2, 2] 目標(biāo)和為 0，固定 -2 和 -1 后，就變成找兩個數(shù)湊 3。雙指針同樣適用：左指針從第三個位置開始，右指針在末尾，根據(jù)和的大小調(diào)整位置。

復(fù)雜度對比很直觀。四數(shù)之和暴力是 O(n?)，四層循環(huán)每個數(shù)都試。優(yōu)化后兩層循環(huán)加雙指針，O(n3)。對于面試常見的 10? 級別數(shù)據(jù)量，這意味著從幾小時運(yùn)算降到幾秒可完成。

雙指針的價值不止這兩道題。它本質(zhì)是利用有序結(jié)構(gòu)的單調(diào)性，把"枚舉所有可能"變成"有方向地收縮搜索空間"。兩數(shù)之和、盛最多水的容器、滑動窗口最大值，底層都是這個思想。掌握之后，看到"有序數(shù)組""找滿足條件的對/組"這類關(guān)鍵詞，本能就會往雙指針方向想。

最后提一個容易踩的坑：去重邏輯必須和指針移動配合好。三數(shù)之和里，找到一組解后，左右指針都要跳過所有相同值再移動，否則 [-1, 0, 0, 0, 1] 這種數(shù)據(jù)會輸出多個 [ -1, 0, 1]。固定元素的循環(huán)也一樣，當(dāng)前數(shù)和前一個相同就直接 continue，避免重復(fù)固定。

這兩道題的代碼實(shí)現(xiàn)細(xì)節(jié)很多，但核心就三點(diǎn)：排序創(chuàng)造單調(diào)性、固定 k-2 個數(shù)把 k 數(shù)之和降為雙指針問題、嚴(yán)格去重保證結(jié)果唯一。把這個框架吃透，五數(shù)之和、六數(shù)之和也能舉一反三。

特別聲明：以上內(nèi)容(如有圖片或視頻亦包括在內(nèi))為自媒體平臺“網(wǎng)易號”用戶上傳并發(fā)布，本平臺僅提供信息存儲服務(wù)。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.