“求字符串中不重復(fù)的最長(zhǎng)子串的長(zhǎng)度”光看這個(gè)題目你可能覺(jué)得平平無(wú)奇但它在算法題單里的地位相當(dāng)特殊LeetCode 原題編號(hào)第 3 題。我面試別人的時(shí)候喜歡拿它當(dāng)開(kāi)場(chǎng)題帶新人刷題也習(xí)慣先讓寫(xiě)這一道。它看起來(lái)就是字符串處理實(shí)際上背后是雙指針加哈希表的經(jīng)典組合吃透這一題后面一連串滑動(dòng)窗口變種題都能順帶拿下。這篇文章我不打算只貼一個(gè)能過(guò)評(píng)測(cè)的答案而是想從頭講清楚幾個(gè)問(wèn)題暴力解法為什么不行滑動(dòng)窗口是怎么自然推出來(lái)的left 指針到底該往哪跳以及 C 實(shí)現(xiàn)里有哪幾個(gè)不寫(xiě)進(jìn)去就會(huì)翻車的細(xì)節(jié)。適合第一次接觸滑動(dòng)窗口的新手、準(zhǔn)備面試刷題的同學(xué)以及那些想把代碼從“能跑”打磨到“穩(wěn)定又高效”的進(jìn)階讀者。1. 先看懂題這道題到底在問(wèn)什么1.1 子串和子序列是兩種完全不同的東西題目說(shuō)的是“最長(zhǎng)子串”不是“最長(zhǎng)子序列”。這兩個(gè)詞在面試?yán)锶绻?tīng)岔了代碼會(huì)完全不一樣。子串要求連續(xù)也就是說(shuō)你切出來(lái)的這一段必須原封不動(dòng)地在原字符串里挨著出現(xiàn)子序列則允許跳著挑字符。舉個(gè)例子字符串a(chǎn)bcabcbb最長(zhǎng)無(wú)重復(fù)子串是abc或者bca長(zhǎng)度都是 3。但是最長(zhǎng)無(wú)重復(fù)子序列可以挑成abc拼上后面的abc嗎不行那里面有重復(fù)字符。實(shí)際上子序列版本要另算題目比子串簡(jiǎn)單不少因?yàn)椴恍枰S護(hù)連續(xù)性。我們這道題的核心難點(diǎn)恰恰就是這個(gè)“連續(xù)”帶來(lái)的窗口約束。還有一個(gè)容易忽略的前提字符重復(fù)是說(shuō)在選中的這一段里沒(méi)有出現(xiàn)兩次相同的字符。比如pwwkew答案是wke或kew長(zhǎng)度 3但pwke不是答案雖然長(zhǎng)度也是 3而且看著更“完整”因?yàn)樗谠锸亲有蛄械皇沁B續(xù)子串。1.2 暴力解法其實(shí)沒(méi)那么不堪但確實(shí)撐不住拿到這道題正常人第一反應(yīng)都是枚舉所有子串逐個(gè)檢查里面有沒(méi)有重復(fù)字符。檢查方式也直接搞一個(gè)集合往里塞字符如果發(fā)現(xiàn)塞不進(jìn)去就說(shuō)明有重復(fù)。枚舉起點(diǎn)i終點(diǎn)j然后 O(len) 檢查整體復(fù)雜度 O(n3)。這個(gè)復(fù)雜度在字符串長(zhǎng)度幾千的時(shí)候還能忍但一旦到幾萬(wàn)就開(kāi)始卡LeetCode 上這題的測(cè)試用例輕松到十幾萬(wàn)O(n3) 直接超時(shí)。我見(jiàn)過(guò)有人寫(xiě)出兩層循環(huán)的“偽優(yōu)化版本”枚舉所有起點(diǎn)然后從起點(diǎn)往后盡量擴(kuò)展邊擴(kuò)展邊檢查重復(fù)。這個(gè)其實(shí)已經(jīng)是 O(n2) 了但面對(duì)十萬(wàn)級(jí)長(zhǎng)度的用例照樣掛。面試官看到這種答案一般會(huì)點(diǎn)點(diǎn)頭然后問(wèn)一句“能不能 O(n)”這時(shí)候就得拿出滑動(dòng)窗口了。1.3 一個(gè)樸素觀察窗口的右邊界不需要回退我們想象自己手里拿著一個(gè)放大鏡從左往右掃描字符串放大鏡框住一段“當(dāng)前窗口”窗口里的字符都互不相同。隨著右邊界往右走新字符可能和窗口里的某個(gè)舊字符撞車。如果撞車我們當(dāng)然可以把左邊界往右挪直到把沖突的那個(gè)字符擠出去。但這里有一個(gè)關(guān)鍵點(diǎn)左邊界永遠(yuǎn)不需要往左回移。因?yàn)榇翱谧兌讨蠹词购竺嬖僬业礁L(zhǎng)的窗口起點(diǎn)也不可能比當(dāng)前這個(gè)左邊界更靠左了。一旦窗口起點(diǎn)往右挪它就再也回不去了。這個(gè)單調(diào)性就是滑動(dòng)窗口算法能成立的根基。你不需要像暴力法那樣重新枚舉起點(diǎn)只要維護(hù)一個(gè)“只往右走”的左邊界和一個(gè)“只往右走”的右邊界兩個(gè)人配合著前進(jìn)所有可能的窗口起點(diǎn)都覆蓋到了。這個(gè)思路聽(tīng)起來(lái)簡(jiǎn)單但怎么把“沖突之后左邊該滑到哪”處理對(duì)才是這道題真正的分水嶺。2. 滑動(dòng)窗口解法的完整推導(dǎo)2.1 窗口的語(yǔ)義一段無(wú)重復(fù)字符的連續(xù)區(qū)間用兩個(gè)索引left和right表示當(dāng)前窗口區(qū)間前閉后閉也就是[left, right]這一段都是合法無(wú)重復(fù)的。right每往前多掃一個(gè)字符就先判斷這個(gè)字符是不是已經(jīng)在窗口里出現(xiàn)過(guò)。如果沒(méi)有出現(xiàn)過(guò)窗口直接擴(kuò)張也就是right窗口長(zhǎng)度變大用當(dāng)前長(zhǎng)度嘗試更新答案。如果出現(xiàn)過(guò)就要?jiǎng)觢eft了。這里的“出現(xiàn)過(guò)”要解釋清楚是出現(xiàn)在當(dāng)前窗口里還是出現(xiàn)在整個(gè)掃描歷史里這兩個(gè)說(shuō)法在不同寫(xiě)法里都有對(duì)應(yīng)的實(shí)現(xiàn)。如果只判斷“整個(gè)歷史出現(xiàn)過(guò)”那left的更新就要配合歷史位置信息如果判斷“當(dāng)前窗口里出現(xiàn)過(guò)”那就要維護(hù)窗口內(nèi)的字符集合。兩種都能得到正確答案但代碼手感和面試觀感差別很大。我用過(guò)窗口內(nèi)集合的做法也用過(guò)歷史位置的做法最終推薦后面一種。因?yàn)樗恍枰趌eft移動(dòng)時(shí)去集合里刪除字符邏輯上更簡(jiǎn)潔而且能把每次left跳轉(zhuǎn)變得更激進(jìn)甚至是直接跳躍而不是一格一格挪。2.2 收縮時(shí)到底跳到哪里max 是防回退的關(guān)鍵假設(shè)掃描到right位置的字符是c并且在更早的位置pos也出現(xiàn)過(guò)一次c。如果pos還在當(dāng)前窗口[left, right-1]里面說(shuō)明沖突了那窗口的左邊界至少得變成pos 1把這個(gè)舊的c隔到窗口外。如果pos已經(jīng)不在當(dāng)前窗口里了說(shuō)明那個(gè)重復(fù)字符早就被滑出去了當(dāng)前這個(gè)c是安全的left不需要?jiǎng)?。所以正確的更新寫(xiě)法是left max(left, lastPos[s[right]] 1);這里的max很容易被漏掉。漏掉之后會(huì)出現(xiàn)什么情況用一個(gè)經(jīng)典例子abba就能解釋。掃描到最后一個(gè)a的時(shí)候lastPos[a]第一次出現(xiàn)在位置 0但當(dāng)前l(fā)eft已經(jīng)滑到 2 了因?yàn)橹虚g處理過(guò)兩個(gè)b的沖突。如果不取maxleft會(huì)被更新成 1窗口變成[1, 3]也就是bba里面就有重復(fù)的b了計(jì)算結(jié)果直接錯(cuò)。所以一定要讓left只會(huì)變大、不會(huì)變小這個(gè)max就是那堵防回退的墻。我個(gè)人第一次寫(xiě)這個(gè)題就栽在漏max上當(dāng)時(shí)調(diào)試了很久輸出老是多了 1一度以為是哈希表更新時(shí)機(jī)的問(wèn)題后來(lái)才定位到是left回退了。這個(gè)坑非常典型后面調(diào)試實(shí)錄里詳細(xì)展開(kāi)。2.3 為什么說(shuō)復(fù)雜度是嚴(yán)格 O(n)很多人以為滑動(dòng)窗口就是兩個(gè)循環(huán)套在一起最壞會(huì)是 O(n2)但其實(shí)是 O(n)。原因在于left和right都只會(huì)單調(diào)遞增right每輪循環(huán)最多走一步left在整個(gè)過(guò)程中最多也只會(huì)走 n 步。每個(gè)字符最多被right碰到一次、被left越過(guò)一次常數(shù)乘 2仍然是線性復(fù)雜度。對(duì)比一下“窗口內(nèi)用集合 逐格收縮”的寫(xiě)法雖然也是 O(n)但left是逐個(gè)字符往外挪的極端情況比如所有字符都一樣窗口會(huì)不斷收縮再擴(kuò)張字符被訪問(wèn)次數(shù)會(huì)變成 2n。用跳躍式更新之后left可以一次性跳到?jīng)_突位置的下一個(gè)位置省掉中間無(wú)意義的比較。從工程角度看這就是“推理正確”和“代碼高效”之間的一個(gè)平衡點(diǎn)。3. C 代碼實(shí)現(xiàn)與細(xì)節(jié)打磨3.1 第一版能跑的代碼用 unordered_map 記錄字符位置直接給一份能過(guò)評(píng)測(cè)的 C 實(shí)現(xiàn)這也是我推薦新手先寫(xiě)出來(lái)的版本class Solution { public: int lengthOfLongestSubstring(string s) { unordered_mapchar, int lastPos; int left 0; int ans 0; for (int right 0; right s.size(); right) { char c s[right]; if (lastPos.count(c) lastPos[c] left) { left lastPos[c] 1; } lastPos[c] right; ans max(ans, right - left 1); } return ans; } };這里判斷重復(fù)的條件是lastPos.count(c) lastPos[c] left意思是“這個(gè)字符出現(xiàn)過(guò)并且上次出現(xiàn)位置還在當(dāng)前窗口里”。也可以用我前面寫(xiě)的另一種寫(xiě)法先無(wú)條件left max(left, lastPos[c] 1)再用lastPos.count(c)來(lái)避免訪問(wèn)不存在的鍵。兩種都可但第二種必須配合默認(rèn)值 0 才能工作如果lastPos里沒(méi)有c且默認(rèn)返回 0則max(left, 1)可能會(huì)錯(cuò)誤地把left提到 1所以我還是推薦上面的判斷寫(xiě)法邏輯更直白。ans的更新放在每次循環(huán)末尾因?yàn)榇藭r(shí)[left, right]一定是一個(gè)合法的無(wú)重復(fù)窗口用當(dāng)前窗口長(zhǎng)度去和答案比一比就好。3.2 哈希表更新的順序不能隨意調(diào)換有個(gè)細(xì)節(jié)值得單獨(dú)說(shuō)lastPos[c] right這行必須在計(jì)算ans之前執(zhí)行而且要在更新left之后執(zhí)行。如果先更新lastPos[c] right再算left那么lastPos[c]反映的就不是“上一次出現(xiàn)的位置”而是“當(dāng)前這次的位置”沖突判斷就失效了整個(gè)代碼會(huì)認(rèn)為是第一次見(jiàn)到這個(gè)字符。還有一個(gè)小眾寫(xiě)法用mapchar, int而不是unordered_map。在 C 里map是紅黑樹(shù)查找 O(log n)雖然這個(gè)題目數(shù)據(jù)量下通常也能過(guò)但沒(méi)必要。unordered_map平均 O(1)優(yōu)先選它。但是unordered_map有一個(gè)隱藏問(wèn)題后面細(xì)說(shuō)。3.3 用數(shù)組替代哈希表性能差距能到幾十倍絕大多數(shù)情況下題目的輸入字符串只包含 ASCII 字符也就是最多 128 種可能。這種前提下完全不需要哈希表用普通數(shù)組就行下標(biāo)直接當(dāng)字符用class Solution { public: int lengthOfLongestSubstring(string s) { int lastPos[128]; fill(lastPos, lastPos 128, -1); int left 0; int ans 0; for (int right 0; right s.size(); right) { char c s[right]; left max(left, lastPos[(unsigned char)c] 1); lastPos[(unsigned char)c] right; ans max(ans, right - left 1); } return ans; } };這個(gè)版本有幾個(gè)坑要注意。第一初始化值必須是-1這樣lastPos[(unsigned char)c] 1就是 0不會(huì)干擾left也不需要判斷字符是否出現(xiàn)過(guò)。第二char在 C 標(biāo)準(zhǔn)里是有符號(hào)還是無(wú)符號(hào)是implementation-defined有些編譯器默認(rèn)char是有符號(hào)的如果字符串里出現(xiàn) ASCII 碼大于 127 的字符直接拿它做下標(biāo)會(huì)變成負(fù)數(shù)數(shù)組越界。穩(wěn)妥做法是強(qiáng)制轉(zhuǎn)成unsigned char保險(xiǎn)起見(jiàn)數(shù)組開(kāi)成128或者256都行我習(xí)慣寫(xiě)成256省心。實(shí)際跑性能測(cè)試的時(shí)候這個(gè)版本和unordered_map版本差距非常明顯。我拿一個(gè) 100 萬(wàn)字符的隨機(jī)串做對(duì)比純屬本地驗(yàn)證不同機(jī)器結(jié)果會(huì)有差異但數(shù)組版一般只需要幾毫秒到十幾毫秒unordered_map版可能需要上百毫秒原因很簡(jiǎn)單unordered_map每次插入或查找要算哈希、做桶定位還可能觸發(fā)擴(kuò)容和 rehash而數(shù)組就是一次隨機(jī)訪問(wèn)。字符集固定且很小的時(shí)候別猶豫用數(shù)組。4. 調(diào)試實(shí)錄與高頻 Bug 復(fù)盤(pán)4.1 Bug 1left 回退輸出莫名其妙變大這個(gè) bug 我前面已經(jīng)預(yù)告過(guò)了是這道題最典型的一個(gè)。癥狀是用abba或abcba這類“字符在窗口外但歷史出現(xiàn)過(guò)”的用例結(jié)果比正確答案大 1 或者更大。根因就是更新left時(shí)沒(méi)有做max保護(hù)直接拿lastPos[c] 1賦值。當(dāng)你處理后面那個(gè)a時(shí)lastPos[a]還是位置 0但窗口左邊界早就跑到 2 了直接覆蓋就成了 1窗口一下子變大里面混進(jìn)了重復(fù)字符。排查方法先跑幾個(gè)小用例abcabcbb、bbbbb、pwwkew如果前兩個(gè)都對(duì)第三個(gè)pwwkew結(jié)果變成 4正確答案是 3那八成就是left回退問(wèn)題。再不行就在循環(huán)里打印left、right、當(dāng)前字符、lastPos[c]觀察left有沒(méi)有變小。修法只有一個(gè)保證left嚴(yán)格單調(diào)不減。4.2 Bug 2窗口左移時(shí)忘了同步哈希表如果你用的是“窗口內(nèi)字符集合”的寫(xiě)法最常見(jiàn)的問(wèn)題是left往前移動(dòng)一格刪掉了一個(gè)字符但是集合里的記錄沒(méi)刪導(dǎo)致后面判斷重復(fù)時(shí)永遠(yuǎn)認(rèn)為字符還在窗口內(nèi)。這個(gè) bug 的癥狀和上一個(gè)正好相反結(jié)果是輸出偏小因?yàn)榇翱诒诲e(cuò)誤地限制住了。這類寫(xiě)法的修復(fù)要點(diǎn)是當(dāng)且僅當(dāng)left右移時(shí)同步從集合中移除s[left]對(duì)應(yīng)的記錄。但既然我們已經(jīng)用“記錄最后出現(xiàn)位置”的跳躍式寫(xiě)法了就完全不用擔(dān)心這個(gè)問(wèn)題。這也是我更推薦跳躍式寫(xiě)法的原因狀態(tài)少一個(gè)bug 就少一截。4.3 邊界條件速查表我把這道題最容易出問(wèn)題的邊界情況整理成一個(gè)表每次寫(xiě)完代碼拿這幾個(gè)例子跑一遍基本能暴露所有實(shí)現(xiàn)問(wèn)題輸入期望輸出備注空串0注意循環(huán)直接不執(zhí)行ans初始為 0單字符a1別把初始ans設(shè)置成奇怪的值全重復(fù)aaaa1驗(yàn)證窗口收縮邏輯全不同abcde5驗(yàn)證窗口擴(kuò)張邏輯沖突在窗口外abba2驗(yàn)證max防回退經(jīng)典用例abcabcbb3面試標(biāo)準(zhǔn)題pwwkew3出現(xiàn)字符w的連續(xù)沖突特別注意abba和abcba。abcba最長(zhǎng)無(wú)重復(fù)子串是abc或cba長(zhǎng)度 3這個(gè)用例對(duì)left回退檢測(cè)特別敏感因?yàn)樽詈蟮腶和開(kāi)頭的a重復(fù)但中間已經(jīng)出現(xiàn)過(guò)b的沖突left已經(jīng)滑到中間了。4.4 一個(gè)容易引起爭(zhēng)論的細(xì)節(jié)哈希表存的是“位置”還是“計(jì)數(shù)”編碼時(shí)有人會(huì)把lastPos存成字符出現(xiàn)的次數(shù)每遇到一個(gè)字符就加一然后在收縮窗口時(shí)把左邊字符的計(jì)數(shù)減一直到所有計(jì)數(shù)都小于等于 1。這種“計(jì)數(shù)法”用在“最多 K 個(gè)不同字符”變體里是必須的但原題用“位置法”更優(yōu)。原因是原題窗口的合法性只要求字符不重復(fù)重復(fù)字符出現(xiàn)時(shí)我們可以精確知道它上次在哪直接跳到那個(gè)位置后面而計(jì)數(shù)法必須一個(gè)字符一個(gè)字符地往外挪雖然復(fù)雜度也是 O(n)但常數(shù)更大。如果一個(gè)面試官看到你寫(xiě)位置法通常會(huì)追問(wèn)一句“如果允許最多出現(xiàn) K 次重復(fù)呢”這就引到下一章的變體了。5. 從這一題延伸出去的滑動(dòng)窗口題單5.1 變體一最多 K 個(gè)不同字符的最長(zhǎng)子串這是原題最常見(jiàn)的變體也是我推薦刷完原題以后馬上練的一道給定一個(gè)字符串找最長(zhǎng)子串要求里面最多包含 K 個(gè)不同字符。原題其實(shí)就是 K字符串長(zhǎng)度因?yàn)榇翱趦?nèi)不能有重復(fù)字符等價(jià)于所有字符出現(xiàn)次數(shù)不超過(guò) 1也等價(jià)于一種特殊的 K。這種題目就必須用“計(jì)數(shù)法”了因?yàn)榇翱诘暮戏ㄐ耘袛嗖辉僖蕾嚒澳硞€(gè)字符的唯一位置”而是依賴“窗口內(nèi)不同字符的數(shù)量”。模板長(zhǎng)這樣int lengthOfLongestSubstringKDistinct(string s, int k) { unordered_mapchar, int count; int left 0, ans 0; for (int right 0; right s.size(); right) { count[s[right]]; while (count.size() k) { if (--count[s[left]] 0) { count.erase(s[left]); } left; } ans max(ans, right - left 1); } return ans; }注意這里left的移動(dòng)用的是while而不是直接跳原因在于“不同字符數(shù)量超了”這個(gè)條件不能直接定位到該刪哪個(gè)字符只能慢慢挪。對(duì)比原題的“跳躍式收縮”你會(huì)更直觀地理解為什么原題能用位置法高效處理因?yàn)樗臎_突信息是精確的而變體里的約束是統(tǒng)計(jì)性的二者本質(zhì)不同。5.2 變體二最小覆蓋子串另一類經(jīng)典題是“找最短子串包含目標(biāo)字符串中的所有字符”典型代表是最小覆蓋子串。它同樣用滑動(dòng)窗口但窗口維護(hù)的目標(biāo)從“最長(zhǎng)”變成了“最短”所以收縮時(shí)機(jī)變成了“當(dāng)窗口已經(jīng)覆蓋所有目標(biāo)字符時(shí)嘗試收縮直到不再覆蓋”再記錄最小值。這類題的核心是維護(hù)一個(gè)need計(jì)數(shù)器記錄目標(biāo)字符還缺幾個(gè)。和原題對(duì)比原題窗口合法性是“內(nèi)部無(wú)重復(fù)”覆蓋類問(wèn)題合法性是“內(nèi)部包含了全部目標(biāo)字符”完全相反但框架一模一樣。所以我一直建議把這幾道題放在一起刷無(wú)重復(fù)字符的最長(zhǎng)子串、最多 K 個(gè)不同字符、最小覆蓋子串、字符串排列。四道題刷完滑動(dòng)窗口這個(gè)技術(shù)就基本刻進(jìn)肌肉記憶了。5.3 面試官追問(wèn)的幾種方向理解原題之后面試官一般會(huì)沿著這幾個(gè)方向繼續(xù)挖如果輸入是數(shù)據(jù)流也就是right不能回退、不能二次讀取怎么處理其實(shí)滑動(dòng)窗口本來(lái)就是單趟掃描天然適合流式輸入。你只需要維護(hù)lastPos每來(lái)一個(gè)字符就按規(guī)則更新left和ans。這倒是原題的一個(gè)天然優(yōu)勢(shì)。如果字符集巨大比如全 Unicode怎么辦數(shù)組方案就廢了得回到unordered_map或者用更高階的字典樹(shù)方案但面試基本不會(huì)要求到那一步。如果字符串特別長(zhǎng)內(nèi)存放不下怎么辦這屬于外部算法題通常切開(kāi)分塊處理塊與塊之間需要小心處理邊界上跨塊的重復(fù)字符復(fù)雜度一下就上去了不是原題能覆蓋的范圍。我自己刷這道題的時(shí)候第一次是用“窗口內(nèi)集合 逐格收縮”寫(xiě)出來(lái)的代碼能過(guò)但也只是能過(guò)。后來(lái)被一個(gè)同事點(diǎn)了一句“你為什么不直接記住每個(gè)字符上次出現(xiàn)的位置”我才意識(shí)到位置法的妙處。從那個(gè)版本開(kāi)始這道題在我手里就變成 5 分鐘默寫(xiě)級(jí)別的題了?，F(xiàn)在每次帶人刷題我都會(huì)建議先理解窗口為什么不需要回退再親手踩一次left回退的坑然后把位置法背下來(lái)。這個(gè)過(guò)程走完滑動(dòng)窗口這關(guān)就算徹底過(guò)了。