婁底網(wǎng)站建設(shè)企業(yè),網(wǎng)站建設(shè)查看框架的源代碼,不用cms怎么做網(wǎng)站,現(xiàn)在都用什么網(wǎng)站找事做引言#xff1a;為什么這道題是算法面試高頻題#xff1f;“最小覆蓋子串”#xff08;LeetCode 76#xff09;是字符串處理領(lǐng)域的經(jīng)典難題#xff0c;也是大廠面試中高頻出現(xiàn)的算法題。它的核心考點(diǎn)是滑動窗口#xff08;雙指針#xff09; 與哈希表的結(jié)合運(yùn)用#xf…引言為什么這道題是算法面試高頻題“最小覆蓋子串”LeetCode 76是字符串處理領(lǐng)域的經(jīng)典難題也是大廠面試中高頻出現(xiàn)的算法題。它的核心考點(diǎn)是滑動窗口雙指針與哈希表的結(jié)合運(yùn)用不僅要求開發(fā)者能寫出正確代碼更需要理解 “動態(tài)窗口優(yōu)化” 的底層邏輯 —— 如何在線性時間內(nèi)找到 “最小且全覆蓋” 的子串避免暴力枚舉的低效陷阱。如果你曾被這道題的復(fù)雜邏輯繞暈或想掌握滑動窗口的通用解題框架本文將從問題分析、思路設(shè)計(jì)、代碼拆解到實(shí)戰(zhàn)延伸帶你一步步吃透這道題。一、問題重述與難點(diǎn)分析1. 問題定義給定兩個字符串 s源字符串和 t目標(biāo)字符串在 s 中找到包含t所有字符的最小子串要求子串中 t 的每個字符出現(xiàn)次數(shù) ≥ 其在 t 中的出現(xiàn)次數(shù)若不存在這樣的子串返回空字符串 。示例輸入s ADOBECODEBANC, t ABC輸出BANC長度為 4是所有滿足條件的子串中最短的2. 核心難點(diǎn)如何快速判斷 “窗口是否覆蓋 t 所有字符”避免逐一比對字符頻次如何在找到有效窗口后快速收縮到 “最小長度”避免冗余字符占用窗口空間如何保證時間復(fù)雜度最優(yōu)暴力枚舉 (O(n^2)) 會超時需優(yōu)化到線性時間二、解題思路滑動窗口 哈希表的黃金組合1. 滑動窗口的核心邏輯滑動窗口本質(zhì)是用兩個指針左指針 i、右指針 j維護(hù)一個動態(tài)區(qū)間 [i, j]通過 “擴(kuò)張 - 收縮” 兩個動作尋找最優(yōu)解擴(kuò)張右指針 j 向右移動將字符加入窗口直到窗口滿足 “覆蓋 t 所有字符”有效窗口收縮左指針 i 向右移動移除窗口內(nèi)的冗余字符非 t 字符或頻次超過需求的 t 字符直到窗口不再滿足條件此時記錄當(dāng)前最小窗口重復(fù) “擴(kuò)張 - 收縮”直到右指針遍歷完 s。2. 哈希表的優(yōu)化設(shè)計(jì)常規(guī)思路是用兩個哈希表一個存 t 的字符需求一個存窗口內(nèi)字符頻次但這樣會增加空間開銷和比對成本。本文代碼采用單哈希表ASCII 數(shù)組實(shí)現(xiàn)雙重功能是核心優(yōu)化點(diǎn)數(shù)組長度設(shè)為 128覆蓋所有 ASCII 字符初始值為 0遍歷 t 時將對應(yīng)字符的哈希值減 1用負(fù)數(shù)標(biāo)記 “需要的字符及次數(shù)”例如 tAAB則 hash[A]-2hash[B]-1遍歷 s 時將窗口內(nèi)字符的哈希值加 1通過哈希值的正負(fù) / 大小判斷字符狀態(tài)哈希值狀態(tài)含義字符是 t 所需且窗口內(nèi)數(shù)量未滿足需求 0該字符是 t 所需且窗口內(nèi)數(shù)量剛好滿足需求 0該字符是冗余窗口內(nèi)數(shù)量超過需求或非 t 字符3. 關(guān)鍵變量設(shè)計(jì)count記錄窗口中 “已滿足需求的 t 字符種類數(shù)”例如 tABC當(dāng)窗口中同時有 A、B、C 且數(shù)量達(dá)標(biāo)時count3minLen存儲最小窗口的長度初始化為 s.length()1確保初始無有效窗口時后續(xù)可更新subLeft存儲最小窗口的左邊界初始化為 -1標(biāo)記無有效窗口。三、代碼逐行拆解帶注釋 邏輯分析class Solution {public:string minWindow(string s, string t) {// 1. 初始化哈希表128位ASCII數(shù)組同時記錄t的需求負(fù)數(shù)和窗口頻次動態(tài)更新vectorint hash(128, 0);for (char c : t) hash[c]--; // 標(biāo)記t中字符的需求需要k個則為-kint sLen s.length(), tLen t.length();int count 0; // 已滿足需求的t字符種類數(shù)達(dá)到t中該字符的需求次數(shù)int minLen sLen 1; // 最小窗口長度初始值大于s的最大可能長度int subLeft -1; // 最小窗口的左邊界初始為-1表示無有效窗口// 2. 滑動窗口核心循環(huán)j是右指針擴(kuò)張窗口i是左指針收縮窗口for (int i 0, j 0; j ; j) {char currentChar s[j]; // 當(dāng)前加入窗口的字符// 2.1 判斷當(dāng)前字符是否是t所需且未滿足需求if (hash[currentChar] 0) {count; // 滿足一種字符的需求count加1}hash[currentChar]; // 窗口中該字符頻次1無論是否是t的字符// 2.2 收縮窗口移除冗余字符hash[s[i]]0表示冗余while (i j hash[s[i]] 0) {hash[s[i]]--; // 冗余字符頻次減1i; // 左指針右移收縮窗口}// 2.3 更新最小窗口僅當(dāng)窗口滿足覆蓋t所有字符counttLen且長度更小時if (count tLen j - i 1 Len) {minLen j - i 1; // 更新最小長度subLeft i; // 更新最小窗口左邊界}}// 3. 返回結(jié)果有有效窗口則截取子串否則返回空字符串return subLeft 0 ? s.substr(subLeft, minLen) : ;}};關(guān)鍵步驟深度解析步驟 1哈希表初始化hash[c]--這一步是代碼的 “巧思核心”。例如 tABC遍歷后 hash[A]-1、hash[B]-1、hash[C]-1其他字符為 0。這樣設(shè)計(jì)的好處是無需額外維護(hù) “需求表” 和 “窗口表”一個數(shù)組搞定兩類信息后續(xù)通過 hash[c] 的正負(fù)可直接判斷字符是否是 t 所需、是否滿足需求。步驟 2右指針擴(kuò)張j每加入一個字符 s[j]先判斷是否是 t 所需且未滿足hash[c]若是則 count 加 1表示多滿足一種字符的需求無論是否是 t 的字符都要 hash[c]更新窗口內(nèi)字符頻次為后續(xù)收縮窗口做準(zhǔn)備。步驟 3左指針收縮i當(dāng) hash[s[i]]0 時說明 s[i] 是冗余字符可能是 t 的字符但頻次超了也可能是非 t 字符此時收縮窗口左指針右移移除該冗余字符同步減少 hash[s[i]] 的值保持頻次準(zhǔn)確收縮過程直到窗口無冗余字符hash[s[i]]確保窗口是 “當(dāng)前右邊界下的最小有效窗口”。步驟 4更新最小窗口只有當(dāng) counttLen窗口覆蓋 t 所有字符時才判斷當(dāng)前窗口是否是最小的若當(dāng)前窗口長度 j-i1 小于 minLen則更新 minLen 和 subLeft這里無需擔(dān)心后續(xù)會有更小的窗口因?yàn)槭湛s過程已保證當(dāng)前窗口是 “最小有效”后續(xù)右指針繼續(xù)擴(kuò)張時會優(yōu)先收縮冗余再判斷是否更新。四、時間 / 空間復(fù)雜度分析1. 時間復(fù)雜度(O(n))(n) 是 s 的長度右指針 j 遍歷 s 一次(O(n))左指針 i 最多收縮 n 次每個字符最多被移除一次(O(n))總操作次數(shù)為 (O(n) O(n) O(n))屬于線性時間效率遠(yuǎn)超暴力枚舉。2. 空間復(fù)雜度(O(1))哈希表是固定長度的數(shù)組128 個元素與輸入字符串長度無關(guān)其他變量count、minLen 等均為常數(shù)級空間因此空間復(fù)雜度為常數(shù)級 (O(1))。五、實(shí)戰(zhàn)技巧與避坑指南1. 常見錯誤點(diǎn)忘記 count 的作用直接比對哈希表所有元素是否 ≥0會導(dǎo)致時間復(fù)雜度升高(O(128n))雖然仍是線性但效率下降收縮窗口時未判斷 i 左指針超過右指針無效窗口初始 minLen 設(shè)為 s.length()當(dāng) s 本身就是最小窗口時會無法更新應(yīng)設(shè)為 s.length()1。2. 同類題延伸滑動窗口通用思路掌握本題的 “滑動窗口 哈希表” 框架后可直接解決以下高頻題LeetCode 3最長無重復(fù)子串用哈希表記錄字符最后出現(xiàn)位置收縮窗口時直接跳到重復(fù)字符后LeetCode 438找到字符串中所有字母異位詞窗口長度固定為 t.length()只需判斷窗口內(nèi)字符頻次是否與 t 一致LeetCode 567字符串的排列與 438 類似窗口長度固定判斷是否是 t 的排列。這些題的核心共性用滑動窗口維護(hù)動態(tài)區(qū)間用哈希表快速判斷區(qū)間是否滿足條件。六、總結(jié)“最小覆蓋子串” 的解題關(guān)鍵的是用單哈希表同時記錄字符需求和窗口頻次通過正負(fù)值簡化判斷滑動窗口的 “擴(kuò)張 - 收縮” 邏輯右指針找有效窗口左指針優(yōu)化最小窗口用 count 變量快速判斷窗口是否覆蓋 t 所有字符避免冗余比對。這道題的優(yōu)化思路體現(xiàn)了算法設(shè)計(jì)的 “極致性”—— 用最少的空間、最低的時間復(fù)雜度解決問題。掌握后你不僅能搞定這道題更能舉一反三應(yīng)對所有滑動窗口類問題。如果在刷題過程中遇到其他疑問或想深入探討滑動窗口的更多應(yīng)用場景歡迎在評論區(qū)交流