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