今天打卡代碼隨想錄Day05。到了這個(gè)節(jié)點(diǎn)算法訓(xùn)練節(jié)奏開始出現(xiàn)一個(gè)明顯轉(zhuǎn)向前四天還在數(shù)組、鏈表這種“元素怎么存、怎么遍歷”的基礎(chǔ)結(jié)構(gòu)里打轉(zhuǎn)從第五天開始題目突然開始頻繁問“這個(gè)元素出現(xiàn)過嗎”“出現(xiàn)了幾次”“能不能快速找到匹配項(xiàng)”。這類問題的核心不再是存儲(chǔ)形式而是查找效率答案幾乎都指向同一個(gè)數(shù)據(jù)結(jié)構(gòu)——哈希表。我剛刷Day05的時(shí)候其實(shí)有點(diǎn)沒轉(zhuǎn)過彎來總覺得哈希表不就是Python里的字典、C里的map嗎查一下能有多大學(xué)問。但真正把四道題刷完才發(fā)現(xiàn)哈希表這套東西“會(huì)用”和“會(huì)用對(duì)”之間差著好幾個(gè)級(jí)別。這篇文章就把我這一天的完整復(fù)盤寫下來包括每道題的解法思路、代碼實(shí)現(xiàn)、以及我在實(shí)際運(yùn)行中踩到的邊界問題給同樣刷到這一天的朋友做個(gè)參考。1. 為什么算法題刷到第五天該輪到哈希表上場了先聊一個(gè)很多人沒認(rèn)真想過的問題前面的數(shù)組和鏈表題本質(zhì)上都在解決“數(shù)據(jù)怎么組織”的問題。到了哈希表專題問題的性質(zhì)變了變成了“數(shù)據(jù)怎么快速查找”。你可以把哈希表理解成一個(gè)超級(jí)快遞柜。數(shù)組和鏈表是貨架你要找一件東西就得順著貨架一格一格看運(yùn)氣好第一格就找到運(yùn)氣不好看到最后才找到?？爝f柜不一樣每件包裹根據(jù)快遞號(hào)直接計(jì)算出一個(gè)柜門編號(hào)你把柜門一開東西就在里面不需要從頭翻到尾。這個(gè)“快遞號(hào)到柜門編號(hào)的轉(zhuǎn)換”就是哈希函數(shù)而那個(gè)柜門背后的空間就是哈希桶。哈希表犧牲了一部分內(nèi)存空間換來的是接近O(1)的查找效率。第五天安排這個(gè)專題正是因?yàn)樵谡鎸?shí)面試題目里判斷存在性、統(tǒng)計(jì)頻率、快速匹配這類需求太常見了靠線性掃描去硬扛幾乎所有相關(guān)題目都會(huì)超時(shí)。我在刷Day05之前其實(shí)也會(huì)用哈希表但用的是“做題家式的用法”——看到字謎題就扔個(gè)Counter看到找兩個(gè)集合公共元素就扔個(gè)set。這種用法沒問題但會(huì)讓我完全感受不到哈希表為什么是這個(gè)性能、什么時(shí)候改選數(shù)組、什么時(shí)候又必須改用真實(shí)哈希結(jié)構(gòu)。代碼隨想錄這一天可貴的地方在于通過四道由淺入深的題把“哈希表解決什么問題、怎么選實(shí)現(xiàn)方式”的邏輯鏈條給你完整串起來了。2. 哈希表的三種形態(tài)數(shù)組、集合、映射怎么選才對(duì)在沒系統(tǒng)刷題之前我總覺得哈希表就是map、dict這一類“鍵值對(duì)容器”。刷完Day05才建立起一個(gè)更準(zhǔn)確的認(rèn)識(shí)只要底層思想是“通過計(jì)算直接定位到桶位置”數(shù)組其實(shí)也算一種哈希表而且很多時(shí)候數(shù)組比真正意義上的哈希結(jié)構(gòu)更高效。2.1 數(shù)組范圍有限時(shí)的最優(yōu)解數(shù)組作為哈希表的核心條件是待標(biāo)識(shí)的“鍵”是有限的、連續(xù)的、范圍可控的整數(shù)。經(jīng)典的就是字母。26個(gè)英文字母你開一個(gè)長度為26的數(shù)組用str[i] - a直接算出下標(biāo)每次操作都是O(1)而且數(shù)組的緩存命中率極高實(shí)際運(yùn)行速度比map快得多。Day05的“有效字母異位詞”就是數(shù)組哈希的教科書場景。異位詞意味著兩個(gè)字符串里各字符出現(xiàn)次數(shù)完全一致你統(tǒng)計(jì)第一個(gè)字符串每個(gè)字母的出現(xiàn)次數(shù)然后遍歷第二個(gè)字符串逐字符減掉次數(shù)最后檢查整個(gè)數(shù)組是否全是0。整個(gè)過程不需要排序不需要存儲(chǔ)復(fù)雜的鍵值結(jié)構(gòu)26個(gè)int就夠了。2.2 集合set只關(guān)心“出現(xiàn)過沒有”當(dāng)數(shù)據(jù)范圍不固定、不需要綁定額外信息、只關(guān)心某個(gè)元素存不存在時(shí)set是最干凈的選擇?！皟蓚€(gè)數(shù)組的交集”第349題就是典型場景。你要判斷數(shù)組1里的每個(gè)元素是否在數(shù)組2里出現(xiàn)過把數(shù)組2轉(zhuǎn)成set然后遍歷數(shù)組1逐一檢查即可。set底層是真實(shí)的哈希結(jié)構(gòu)插入和查找平均都是O(1)但它比數(shù)組多了一層哈希計(jì)算實(shí)際耗時(shí)略高。另一個(gè)值得注意的點(diǎn)是set天然去重這正好滿足交集題目“輸出唯一元素”的要求省得自己再寫去重邏輯。2.3 map鍵值對(duì)應(yīng)關(guān)系才是剛需map在所有哈希表形態(tài)里最重量級(jí)因?yàn)樗凇按嬖谛耘袛唷敝线€附加了“關(guān)聯(lián)信息”。Day05的重頭戲“兩數(shù)之和”就是map的標(biāo)準(zhǔn)場景。光知道某個(gè)數(shù)字出現(xiàn)過不行你還得知道它出現(xiàn)在哪個(gè)位置需要在哈希表的value里存下標(biāo)。我自己的選型經(jīng)驗(yàn)是看到題先問自己三個(gè)問題——鍵的范圍是否固定且小如果固定且小直接用數(shù)組需不需要去重和判斷存在需要就去重用set需不需要為每個(gè)鍵記錄附加數(shù)據(jù)需要就直接上map。這三步下來基本不會(huì)選錯(cuò)結(jié)構(gòu)。Day05四道題恰好把這三條分支全部覆蓋了一遍刷完以后我對(duì)哈希結(jié)構(gòu)怎么選就有了肌肉記憶。3. Day05四道哈希表題從思路到代碼逐題拆解這一天我在代碼隨想錄打卡的題目分別是242.有效的字母異位詞、349.兩個(gè)數(shù)組的交集、202.快樂數(shù)、1.兩數(shù)之和。整體難度不高但每一題都對(duì)應(yīng)一個(gè)哈希表的典型應(yīng)用模式拆開來說清楚。3.1 第242題有效的字母異位詞用數(shù)組哈希完成“字符頻次比對(duì)”題目本身不難理解給定兩個(gè)字符串s和t判斷t是不是s的字母異位詞也就是兩個(gè)字符串包含的字母完全相同只是排列順序不同。最無腦的做法是對(duì)兩個(gè)字符串排序后直接比較時(shí)間復(fù)雜度O(n log n)。哈希表思路則能把復(fù)雜度壓到O(n)因?yàn)樽址邢抻靡粋€(gè)長度為26的數(shù)組即可。bool isAnagram(string s, string t) { if (s.size() ! t.size()) return false; vectorint record(26, 0); for (char c : s) { record[c - a]; } for (char c : t) { record[c - a]--; } for (int count : record) { if (count ! 0) return false; } return true; }這里我想特別強(qiáng)調(diào)一個(gè)我在實(shí)際提交時(shí)踩過的坑不要忘記先判斷兩個(gè)字符串長度是否相等。這是異位詞的必要條件但也是一個(gè)特別容易被忽略的初始剪枝。不判斷長度直接統(tǒng)計(jì)最后數(shù)組全為0也能通過但多做了很多無意義的遍歷也不夠嚴(yán)謹(jǐn)。還有一個(gè)小優(yōu)化思路第二步遍歷t的時(shí)候如果減到某個(gè)字符的計(jì)數(shù)已經(jīng)小于0說明t里該字符出現(xiàn)次數(shù)超過了s可以直接返回false不需要等到最后統(tǒng)一檢查。我實(shí)測下來這個(gè)提前返回對(duì)包含大量重復(fù)字符的長字符串有明顯加速效果。3.2 第349題兩個(gè)數(shù)組的交集核心是用set完成去重與存在性判斷這題要求返回兩個(gè)數(shù)組的交集且結(jié)果中每個(gè)元素必須唯一。第一反應(yīng)可能會(huì)是雙重循環(huán)暴力查找時(shí)間復(fù)雜度O(n*m)在LeetCode上勉強(qiáng)能過但在面試手寫環(huán)節(jié)基本屬于下乘答案。更好的解法是先建一個(gè)set存nums1的元素再遍歷nums2逐個(gè)檢查是否在set里。這里有個(gè)細(xì)節(jié)需要注意結(jié)果必須去重所以不能把符合條件的結(jié)果直接存進(jìn)vector得再套一個(gè)set去重或者用一個(gè)標(biāo)記數(shù)組記錄哪些元素已經(jīng)加入結(jié)果。我是用C寫的核心代碼如下vectorint intersection(vectorint nums1, vectorint nums2) { unordered_setint set1(nums1.begin(), nums1.end()); unordered_setint resultSet; for (int num : nums2) { if (set1.count(num)) { resultSet.insert(num); } } return vectorint(resultSet.begin(), resultSet.end()); }這里選unordered_set而不是set是個(gè)小講究。set底層是紅黑樹插入和查找是O(log n)unordered_set底層才是真正意義上的哈希表平均O(1)。在只關(guān)心存在性、不需要有序遍歷的場景里前者總是更快。還有值得一提的邊界場景兩個(gè)數(shù)組都為空、一個(gè)為空、二者沒有任何交集這幾類情況用set寫法都能天然處理不需要額外寫分支。這也是哈希表解法相比雙指針掃描更省心的原因。3.3 第202題快樂數(shù)哈希表保存的是“循環(huán)檢測的狀態(tài)”這道題很能迷惑人因?yàn)轭}目本身看起來跟哈希表八竿子打不著給定一個(gè)正整數(shù)每次將該數(shù)替換為它每個(gè)位置上的數(shù)字的平方和重復(fù)這個(gè)過程。如果最終能變?yōu)?就是快樂數(shù)如果陷入不包含1的循環(huán)就不是快樂數(shù)。我第一次做這題想的是“直接模擬100次變不成1就是假的”這種解法本質(zhì)上依賴一個(gè)沒有依據(jù)的假設(shè)。正確思路是把“是否出現(xiàn)過這個(gè)數(shù)”作為循環(huán)判定的依據(jù)——如果某個(gè)平方和結(jié)果重復(fù)出現(xiàn)說明已經(jīng)進(jìn)入循環(huán)永遠(yuǎn)不可能變成1。bool isHappy(int n) { unordered_setint seen; while (n ! 1 !seen.count(n)) { seen.insert(n); int sum 0; while (n 0) { int digit n % 10; sum digit * digit; n / 10; } n sum; } return n 1; }我實(shí)測這里有個(gè)挺大的坑是取各個(gè)位上的數(shù)字。新手容易寫成先to_string(n)然后把每個(gè)char轉(zhuǎn)int這種寫法本身沒錯(cuò)但會(huì)引入字符串轉(zhuǎn)換的開銷而且char到int的轉(zhuǎn)換容易出錯(cuò)。直接用% 10和/ 10把每一位剝離出來是更干凈的寫法。另外一個(gè)可選的進(jìn)階方案是快慢指針。用兩個(gè)變量一個(gè)每次計(jì)算一次平方和一個(gè)每次計(jì)算兩次如果存在循環(huán)二者一定在某個(gè)時(shí)刻相遇。這個(gè)思路不需要哈希表空間復(fù)雜度降到O(1)非常適合作為面試中的延伸題展示自己思路開闊。3.4 第1題兩數(shù)之和哈希表map把O(n2)暴力降到O(n)這題算得上LeetCode的“天下第一題”刷題數(shù)超過1900萬次。問題很簡單給一個(gè)數(shù)組和一個(gè)目標(biāo)值找出數(shù)組中兩個(gè)數(shù)和為目標(biāo)值的下標(biāo)。暴力雙重循環(huán)肯定能過但Day05的重點(diǎn)是讓你掌握哈希表優(yōu)化。我在這題上犯過一個(gè)特別典型的錯(cuò)誤而且相信很多人在初學(xué)時(shí)會(huì)犯同樣的錯(cuò)先把自己當(dāng)前遍歷的元素插入哈希表然后去查找目標(biāo)差值。這樣做在遇到重復(fù)值時(shí)會(huì)把自己匹配給自己。比如數(shù)組是[3, 3]目標(biāo)值是6遍歷第一個(gè)3時(shí)先插入然后查6-33結(jié)果發(fā)現(xiàn)map里剛插入的3下標(biāo)也是0返回[0,0]這顯然是錯(cuò)的。標(biāo)準(zhǔn)解法是遍歷過程中先查目標(biāo)差值查不到再把當(dāng)前值及其下標(biāo)插入哈希表。這樣每個(gè)下標(biāo)只會(huì)在后面的遍歷中被其他元素匹配到不會(huì)自我匹配。vectorint twoSum(vectorint nums, int target) { unordered_mapint, int hash; for (int i 0; i nums.size(); i) { int need target - nums[i]; if (hash.count(need)) { return {hash[need], i}; } hash[nums[i]] i; } return {}; }關(guān)于map的count和findC里map.count(key)返回0或1比find寫起來更直觀但兩者性能沒有本質(zhì)區(qū)別。另外要注意如果題目要求返回所有滿足條件的下標(biāo)對(duì)寫法又不一樣需要map里存下標(biāo)列表。Day05只要求任意一對(duì)所以上面的寫法就夠了但在面試延伸時(shí)最好能主動(dòng)提到這個(gè)變體。4. 我實(shí)測一天四題下來最容易翻車的是這五個(gè)細(xì)節(jié)四道題本身不算難但在LeetCode實(shí)際提交過程中我反復(fù)翻車的地方集中在下面幾個(gè)細(xì)節(jié)。這些內(nèi)容代碼隨想錄的正文里有提到但真正感受深刻還是要自己踩一遍。第一個(gè)是數(shù)組哈希的下標(biāo)越界。有效字母異位詞那題如果用record[c - a]來做必須保證輸入只包含小寫字母。題目確實(shí)這么限制了但如果把代碼拿到本地測試輸入一個(gè)大寫字母就會(huì)出負(fù)數(shù)下標(biāo)。我在本地調(diào)試時(shí)給過一個(gè)帶大寫字母的用例程序直接崩潰。實(shí)際項(xiàng)目里字符串輸入基本不可能那么干凈所以刷題時(shí)養(yǎng)成“先確認(rèn)字符范圍再?zèng)Q定數(shù)組大小”的習(xí)慣很有價(jià)值。第二個(gè)是set處理負(fù)數(shù)哈希的實(shí)際問題。如果用數(shù)組下標(biāo)來標(biāo)記某個(gè)數(shù)出現(xiàn)過遇到負(fù)數(shù)就得做偏移。LeetCode第349題的題面雖然沒直接給負(fù)數(shù)用例但我在本地測試時(shí)用了一組負(fù)數(shù)才發(fā)現(xiàn)數(shù)組哈希需要手動(dòng)偏移代碼寫起來就不如set優(yōu)雅了。這種“選型失敗”的時(shí)刻越多越能體會(huì)到前面說合理選型的重要性。第三個(gè)是在快樂數(shù)里寫死模擬次數(shù)。這個(gè)錯(cuò)誤在網(wǎng)上很常見有人直接寫while循環(huán)100次甚至1000次理由是“不循環(huán)超過1000次肯定不是快樂數(shù)”。這不能算錯(cuò)但它沒有一個(gè)扎實(shí)的理論根據(jù)而且如果面試官追問“為什么不是999次”就會(huì)卡住。用哈希表記錄歷史狀態(tài)才是真正無懈可擊的做法它直接利用了“一旦重復(fù)必然循環(huán)”的數(shù)學(xué)性質(zhì)。第四個(gè)是兩數(shù)之和里“先插后查”的自我匹配。我前面已經(jīng)詳細(xì)寫過了這里再強(qiáng)調(diào)一次就是插入和查找的先后順序決定了算法正確性建議大家在腦子里把這個(gè)過程完整推演幾遍比單純記住“先查后插”更能應(yīng)付變種題。第五個(gè)是輕視哈希表的空間開銷。有些題目確實(shí)能用哈希表把時(shí)間壓到最低但代價(jià)是額外空間。比如兩數(shù)之和的暴力解法空間O(1)哈希解法空間O(n)。如果面試官要求原地處理或者數(shù)據(jù)規(guī)模大到內(nèi)存吃緊你還得回到排序加雙指針那條路上。所以Day05刷完后我有意識(shí)地補(bǔ)充做了349題的排序雙指針版本算是對(duì)哈希解法的對(duì)照理解。5. 哈希表專題刷完我給自己的學(xué)習(xí)節(jié)奏和復(fù)盤方式代碼隨想錄的Day05是哈希表專題的開端后面還有幾道進(jìn)階題在等著但這一天的四道題足以建立一個(gè)清晰的方法框架。我自己的學(xué)習(xí)節(jié)奏是這樣安排的早上先通讀一遍題目不急著看答案自己先試著解每道題無論能不能解出來都先記錄自己的想法之后對(duì)照代碼隨想錄的思路重點(diǎn)看自己遺漏了哪個(gè)關(guān)鍵點(diǎn)。對(duì)哈希表這類題目我還有一個(gè)特別想推薦的做法用“一句話總結(jié)每道題的功能模式”。我在筆記里給這四道題分別寫了四句話——字母異位詞是“用數(shù)組統(tǒng)計(jì)頻次”兩個(gè)數(shù)組的交集是“用set做去重存在性”快樂數(shù)是“用set檢測循環(huán)”兩數(shù)之和是“用map記錄匹配項(xiàng)與下標(biāo)”。這四句話看著簡單但每句話都是解題思路的高度濃縮復(fù)習(xí)的時(shí)候掃一眼就能把整個(gè)解題上下文調(diào)出來。復(fù)盤時(shí)我還習(xí)慣把每道題的錯(cuò)誤提交記錄翻一遍分析錯(cuò)因。我統(tǒng)計(jì)了Day05這四道題兩數(shù)之和的“先插后查”錯(cuò)誤、快樂數(shù)的“忘記用狀態(tài)去重”、字母異位詞的“忘記長度剪枝”這三個(gè)是我個(gè)人最高頻的錯(cuò)誤類型分別對(duì)應(yīng)哈希表結(jié)構(gòu)使用順序、哈希表功能誤判、以及初始條件考慮不全。知其然更知其所以然后面的進(jìn)階題才不至于反復(fù)在同一個(gè)坑里翻車。Day05給我的整體感受是哈希表不是一種需要死記硬背數(shù)據(jù)結(jié)構(gòu)的專題而是一種思維方式的切換。它讓你在遇到“查找、去重、關(guān)聯(lián)”這類問題時(shí)天然地放棄笨重的線性遍歷轉(zhuǎn)而思考“怎么算出一個(gè)定義域內(nèi)確定的位置”。這種思維一旦建立后面刷滑動(dòng)窗口、二叉樹路徑、圖遍歷時(shí)的很多緩存和去重操作都會(huì)順手得多。如果你現(xiàn)在也在按代碼隨想錄的節(jié)奏刷題這一天值得放慢一點(diǎn)把四道題都吃透比囫圇吞棗多刷好幾道更有價(jià)值。