之和C++解法拆解：從暴力枚舉到哈希表優(yōu)化)
兩數(shù)之和這道題在力扣平臺上的編號是第一題路徑是“力扣——1”也是絕大多數(shù)人打開刷題生涯的那扇門。它本身并不難但作為C入門選手第一道題往往決定了你后續(xù)刷題的姿勢和手感所以我一直覺得有必要把它拆透了講。這篇不說廢話直接圍繞題面、三種層級的解法演進(jìn)、C代碼逐行實(shí)現(xiàn)、本地環(huán)境配置、常見坑點(diǎn)展開把這道題吃干抹凈。1. 題面與核心需求拆解1.1 題目到底在問什么原題是這樣的給定一個整數(shù)數(shù)組nums和一個整數(shù)目標(biāo)值target請在數(shù)組中找出和為目標(biāo)值target的那兩個整數(shù)并返回它們的數(shù)組下標(biāo)。示例輸入nums [2,7,11,15], target 9 輸出[0,1] 解釋因?yàn)?nums[0] nums[1] 9返回 [0, 1]注意這里問的不是“值”而是“下標(biāo)”。很多人第一次做的時候答案對了但輸出的是數(shù)組元素本身結(jié)果直接判錯。力扣要求返回的是vectorint里面裝的是兩個索引這個細(xì)節(jié)必須盯死。題目還給了兩個隱含保證一是每種輸入只會對應(yīng)一個答案這意味著你不用處理“多組答案”的情況看到一組配直接返回就行二是數(shù)組中同一個元素不能使用兩遍。這句話很多人沒讀懂我解釋一下它不是說你不能選兩個相同的值而是說一個下標(biāo)不能用兩次。比如nums [3, 3]target 6是合法輸入答案是[0, 1]兩個3是不同的下標(biāo)但如果你拿著同一個下標(biāo)算兩次比如nums[i] nums[i]那是被禁止的。1.2 從題面里挖出的約束條件這道題的輸入規(guī)模在力扣上現(xiàn)在已經(jīng)加強(qiáng)過了數(shù)組長度最多能到10^4甚至10^5級別。這意味著什么意味著 O(n^2) 的暴力解在最壞情況下要做大約 10^8 到 10^10 次操作放到老版本的數(shù)據(jù)上也許能蒙混過關(guān)放到現(xiàn)在的評測數(shù)據(jù)里基本會超時。目標(biāo)值target和數(shù)組元素都是整數(shù)可正可負(fù)不排除有負(fù)數(shù)的情況。很多人拿到題目就默認(rèn)所有數(shù)都是正的結(jié)果測試一跑就掛在負(fù)數(shù)用例上。實(shí)際上target - nums[i]完全可能是負(fù)數(shù)這不影響哈希表的查找但會影響你自己手寫“剪枝”之類的優(yōu)化時的心態(tài)。還有一個隱含信息返回值順序沒有要求你可以返回[0, 1]也可以返回[1, 0]。這個自由度給了哈希表解法一定的容錯空間也讓我們在實(shí)現(xiàn)時不用糾結(jié)先存誰后取誰。2. 解法演進(jìn)從暴力到哈希表2.1 暴力枚舉最直覺但最容易超時的方案很多人的第一反應(yīng)是兩層循環(huán)掃描外層固定一個數(shù)內(nèi)層從它后面找配對的數(shù)。代碼大概長這樣class Solution { public: vectorint twoSum(vectorint nums, int target) { int n nums.size(); for (int i 0; i n; i) { for (int j i 1; j n; j) { if (nums[i] nums[j] target) { return {i, j}; } } } return {}; } };這個方案的時間復(fù)雜度是 O(n^2)空間復(fù)雜度 O(1)。它簡單、直觀、不容易錯但有一個致命問題數(shù)組一大就歇菜。力扣現(xiàn)在的數(shù)據(jù)規(guī)模下n 10^5時n^2就是 10^10哪怕每次比較只消耗幾個時鐘周期整體也要幾十秒量級評測系統(tǒng)直接判超時。我見過不少初學(xué)者死磕暴力解提交超時后一臉茫然其實(shí)這里需要的不是“更快的暴力”而是換一種查找思路。暴力解慢的根本原因是內(nèi)層循環(huán)每次都在線性掃描判斷“有沒有一個數(shù)等于 target - nums[i]”這件事花費(fèi)了 O(n) 的時間。如果我們把“查找某個值是否存在”的時間從 O(n) 降到 O(1)總復(fù)雜度自然就下來了。2.2 哈希表用空間換時間的經(jīng)典思路哈希表或者說 C 里的unordered_map干的事情就是把值映射到它的位置。你可以理解為它給所有數(shù)字建了一張“索引表”每次想找某個數(shù)有沒有出現(xiàn)過按鍵查一下就行平均只需 O(1) 時間?；谶@個思路算法變成遍歷數(shù)組每到一個元素nums[i]先算complement target - nums[i]去哈希表里查這個complement是否存在存在說明之前已經(jīng)遍歷到過這個數(shù)直接返回它對應(yīng)的下標(biāo)和當(dāng)前下標(biāo)i不存在就把nums[i]和它的下標(biāo)i存進(jìn)哈希表繼續(xù)遍歷。這里的關(guān)鍵是先查后存順序不能亂。原因后面在避坑部分會詳細(xì)說這里先記住這個原則。2.3 為什么一次遍歷就夠很多人對“一次遍歷”感到不踏實(shí)總覺得得先把全部元素放進(jìn)哈希表再從頭查一遍才能保證找全。其實(shí)大可不必。舉個例子nums [2, 7, 11, 15]target 9。遍歷到2的時候complement 7哈希表里沒有 7于是把2 - 0存進(jìn)去遍歷到7的時候complement 2一查哈希表2在 0 號位存著呢直接返回[0, 1]。你發(fā)現(xiàn)沒有當(dāng)你遍歷到任何一個元素的時候它前面的所有元素都已經(jīng)入表了。如果配對的數(shù)是它前面的某一個那么一定能查到如果配對的數(shù)在它后面那現(xiàn)在是查不到的但等遍歷到后面那個數(shù)的時候當(dāng)前元素已經(jīng)入表到時照樣能查到。所以一次遍歷就夠了不存在漏掉的情況。這個“一邊查一邊存”的模式在力扣里大量出現(xiàn)比如后面會遇到的三數(shù)之和、兩數(shù)之和系列變體本質(zhì)上都是這個套路。把第一題的哈希思維吃透后面會輕松很多。3. C代碼的逐行實(shí)現(xiàn)與細(xì)節(jié)3.1 完整代碼和提交模板我們直接上最終版本這是我在本地和力扣上都驗(yàn)證過的寫法#include vector #include unordered_map class Solution { public: vectorint twoSum(vectorint nums, int target) { unordered_mapint, int hash; // 值 - 下標(biāo) for (int i 0; i nums.size(); i) { int complement target - nums[i]; auto it hash.find(complement); if (it ! hash.end()) { return {it-second, i}; } hash[nums[i]] i; } return {}; } };在力扣的提交環(huán)境里vector和unordered_map的頭文件已經(jīng)默認(rèn)包含所以很多題解里不會寫#include。但你在本地跑的時候必須自己補(bǔ)上否則編譯直接報錯。我建議即使是在力扣頁面寫代碼也養(yǎng)成把頭文件寫全的習(xí)慣這樣切到本地調(diào)試的時候不用額外改。這里有幾個C的點(diǎn)需要解釋一下尤其是新手容易卡住的地方。3.2 為什么用 unordered_map 而不是 mapC 標(biāo)準(zhǔn)庫里有兩個容器都能做鍵值映射一個是map底層是紅黑樹插入查找都是 O(log n) 的另一個是unordered_map底層是哈希表插入查找平均 O(1)。這道題只要求“能不能快速找到某個值”不要求按順序遍歷鍵。所以選擇unordered_map是更合適的它在n較大時優(yōu)勢明顯。map雖然也能通過但 O(log n) 和 O(1) 在數(shù)據(jù)量大的時候差距會體現(xiàn)出來。還有一個隱藏區(qū)別是頭文件不同unordered_map需要#include unordered_mapmap需要#include map。別搞混。3.3 返回值與邊界處理函數(shù)簽名是vectorint twoSum(vectorint nums, int target)返回類型是vectorint。所以我們返回的時候可以用花括號初始化列表return {it-second, i};這個寫法是 C11 之后支持的本質(zhì)上是用initializer_list構(gòu)造一個臨時vector并返回。如果你用的是更老的編譯器標(biāo)準(zhǔn)可能會報錯所以本地編譯的時候我建議至少開-stdc11我個人習(xí)慣直接用 C17。至于最末尾的return {};其實(shí)是返回一個空 vector。正常情況下不會執(zhí)行到這里因?yàn)轭}目保證有且只有一個答案但這行代碼能讓編譯器滿意覆蓋掉“函數(shù)可能沒有返回值”的告警。有些強(qiáng)迫癥可能會直接寫return {-1, -1};或者return {0, 0};也行不影響正確性就是語義上不如空 vector 干凈。再強(qiáng)調(diào)一下auto it hash.find(complement)。find返回的是一個迭代器類型寫全了是unordered_mapint, int::iterator太長了用auto省心。判斷是否存在就看它是否等于hash.end()。這里新手最容易犯的錯是直接寫hash[complement]結(jié)果查一個不存在的鍵時operator[]會悄悄把這個鍵插入并賦默認(rèn)值 0導(dǎo)致下標(biāo)返回 0邏輯直接搞亂。記住查用find插用operator[]或insert不要拿operator[]干查找的活。4. 實(shí)操過程從本地環(huán)境到提交通過4.1 把 VSCode 調(diào)成刷題順手的環(huán)境力扣網(wǎng)頁端可以直接寫代碼提交但很多人還是喜歡在本地跑。原因很簡單本地能斷點(diǎn)調(diào)試、能加打印、能反復(fù)實(shí)驗(yàn)比在網(wǎng)頁端看著報錯干瞪眼強(qiáng)太多。雖然題目寫完了都能通過但調(diào)試的過程才是真正學(xué)到東西的過程。我用的是 VSCode配合 C/C 擴(kuò)展配置一次之后刷題非常順手。你需要準(zhǔn)備VSCode一個 C 編譯器Windows 上可以用 MinGW-w64 或者 MSVCmacOS 上可以用 Xcode Command Line Tools 自帶的 clangC/C 擴(kuò)展編譯器安裝完之后在終端里輸入g --version能輸出版本號就說明環(huán)境沒問題。然后要創(chuàng)建一個tasks.json負(fù)責(zé)編譯。我通常的做法是給刷題建一個單獨(dú)的目錄比如leetcode里面每個題一個文件夾第1題就在0001_two_sum下放一個main.cpp。main.cpp里除了放Solution類再寫一個簡單的測試main函數(shù)把示例和邊界用例都跑一遍int main() { Solution sol; vectorint nums1 {2, 7, 11, 15}; vectorint res1 sol.twoSum(nums1, 9); for (int x : res1) cout x ; // 輸出 0 1 cout endl; vectorint nums2 {3, 3}; vectorint res2 sol.twoSum(nums2, 6); for (int x : res2) cout x ; // 輸出 0 1 cout endl; vectorint nums3 {-3, 4, 3, 90}; vectorint res3 sol.twoSum(nums3, 0); for (int x : res3) cout x ; // 輸出 0 2 cout endl; return 0; }至于編譯運(yùn)行為什么不直接在終端敲命令其實(shí)可以敲但不是每個人都想背一長串g -stdc17 main.cpp -o main。配置好tasks.json之后按CtrlShiftB就能一鍵編譯再按 F5 就能啟動調(diào)試。VSCode 的launch.json里把externalConsole或者internalConsole配好命中斷點(diǎn)之后能清清楚楚看到hash表里存了什么值、complement是多少、迭代器指向哪里。這個調(diào)試過程對新手尤其有幫助。我自己刷題前兩年相當(dāng)一部分容易混淆的概念比如迭代器失效、引用傳參、返回值優(yōu)化都是在斷點(diǎn)面板里反復(fù)看出來的。4.2 關(guān)鍵的調(diào)試用例設(shè)計很多人刷題只跑一遍示例就提交過了就算數(shù)沒過就干瞪眼。稍微好一點(diǎn)的做法是準(zhǔn)備幾組典型的測試數(shù)據(jù)每組數(shù)據(jù)都帶著不同的邊界含義。這道題我建議至少準(zhǔn)備四組測試用例target期望結(jié)果驗(yàn)證點(diǎn)[2, 7, 11, 15]9[0, 1]官方示例標(biāo)準(zhǔn)情況[3, 3]6[0, 1]兩個相同數(shù)值不同下標(biāo)[-3, 4, 3, 90]0[0, 2]存在負(fù)數(shù)target減完為負(fù)[1]2空數(shù)組過短題目不會出現(xiàn)但代碼要兜底第一組測的是最基本的功能第二組測的是“同一元素不能使用兩遍”這個約束是否被正確處理第三組測的是負(fù)數(shù)鍵在unordered_map里能否正常索引第四組是防御性測試雖然題目保證一定有答案但萬一你代碼里存在空指針或者越界風(fēng)險這組能幫你提前暴露。4.3 如果一切順利提交時還有什么要檢查本地跑通了之后去力扣頁面上提交有幾點(diǎn)容易忽略第一提交的時候類名和函數(shù)簽名必須和題目完全一致大小寫、參數(shù)類型、返回類型都不能改。力扣的評測系統(tǒng)是拿固定的測試代碼調(diào)用你的Solution::twoSum你改了簽名就編譯不過。第二返回值順序沒有要求但有些同學(xué)本地測試時自己用vectorint比較結(jié)果嚴(yán)格匹配[0, 1]由于題目允許[1, 0]這種比較方式并不嚴(yán)謹(jǐn)。如果你想寫自動化驗(yàn)證最好把結(jié)果排序后再比較或者用set存下兩個值再比對。第三提交前把頭文件相關(guān)的#include刪掉其實(shí)不影響因?yàn)榱郗h(huán)境自動包含了。但如果你連std::前綴都省了可能會導(dǎo)致命名沖突。穩(wěn)妥起見全部按標(biāo)準(zhǔn)寫法來。5. 常見問題與避坑實(shí)錄5.1 最容易踩的幾個坑第一個坑把整個數(shù)組先塞進(jìn)哈希表再開始查找。這個做法錯在哪看這個用例nums [3, 3]target 6。如果你第一步把整個數(shù)組遍歷一遍存進(jìn)哈希表因?yàn)殒I是值、值是下標(biāo)兩個 3 的鍵相同后面的下標(biāo)會把前面的覆蓋掉最終hash[3] 1。然后你從頭再來一遍遍歷到下標(biāo) 0 時complement 3一查哈希表發(fā)現(xiàn) 3 存在返回的答案是[1, 0]。這道題答案允許任意順序所以這個用例僥幸通過了。但換個場景nums [3, 2, 3]target 6同樣先塞后查最終hash[3] 2遍歷到下標(biāo) 0 時返回[2, 0]依然能通過?？雌饋砗孟窨偸悄芡ㄟ^但這不是因?yàn)檫壿嬚_而是因?yàn)槟愕闹当弧案采w成最后一個同值下標(biāo)”后碰巧仍滿足題目“返回任意順序”的要求?？梢坏╊}目改成“下標(biāo)也必須按原順序返回”或者存在多個同值元素時這個覆蓋就會造成錯誤。所以規(guī)范的做法永遠(yuǎn)是“先查再存”這不僅是性能問題更是邏輯嚴(yán)謹(jǐn)性的問題。第二個坑用hash[complement]判斷鍵是否存在。我上面提過operator[]在鍵不存在時會自動插入默認(rèn)值 0。假設(shè)nums [2, 7]target 9這種簡單例子第一次循環(huán)查complement 7不存在hash[7]會被插入一個值為 0 的條目。第二次循環(huán)查到 2它返回的哈希表值是 0恰好是正確下標(biāo)所以你誤以為代碼沒問題。但假如complement的值在數(shù)組里根本不存在hash[complement]會返回 0讓你誤以為下標(biāo) 0 就是答案直接返回了錯誤的[0, i]。這就是為什么必須用find實(shí)在要用count也可以但不要直接用operator[]查。第三個坑返回下標(biāo)時把順序?qū)懛础Ｕ_邏輯是complement存在哈希表里it-second是配對值之前入表時的下標(biāo)i是當(dāng)前下標(biāo)。有些同學(xué)邏輯跑通后下意識寫成return {i, it-second}測試用例里如果兩個下標(biāo)恰好是對稱的可能也能通過但一旦順序反了且測試用例要求特定順序就會掛。這道題不要求順序但為了養(yǎng)成好習(xí)慣還是按照“先查到的放前面當(dāng)前的放后面”來寫。第四個坑認(rèn)為nums.size()的返回值可以直接拿來當(dāng)int用。size()返回的是size_t在 64 位系統(tǒng)上是unsigned long long。刷題時基本不會出問題但如果你寫for (int i 0; i nums.size(); i)編譯器會有符號比較的告警。我一般直接寫int n nums.size();后再用n循環(huán)或者用size_t i。5.2 話不多說關(guān)聯(lián)擴(kuò)展題該往哪走兩數(shù)之和只是一系列問題的起點(diǎn)。刷完這道題你最應(yīng)該趁熱打鐵做以下幾類力扣 167兩數(shù)之和 II - 輸入有序數(shù)組。同樣是兩數(shù)之和但數(shù)組有序可以用雙指針做到 O(1) 空間這和哈希表解法思路完全不同。力扣 15三數(shù)之和。把“兩個數(shù)的和”擴(kuò)展成“三個數(shù)和為0”核心思路是先排序再雙指針哈希表的地位被削弱了。力扣 121買股票的最佳時機(jī)。這個題不是兩數(shù)之和的變體但同樣是“一次遍歷維護(hù)狀態(tài)”的經(jīng)典場景和哈希表的“邊查邊存”有異曲同工之處。我一直覺得刷題不能只滿足于 AC 一道題。把一道題吃透再沿著它的變體往下走整個知識網(wǎng)絡(luò)就串起來了。兩數(shù)之和背后那個“查找表”的抽象其實(shí)在真實(shí)開發(fā)中也經(jīng)常用到比如緩存鍵值對、去重、索引構(gòu)建本質(zhì)都是哈希表的應(yīng)用。6. 一點(diǎn)私貨我的刷題習(xí)慣說了這么多最后分享一個我自己的習(xí)慣。每次 AC 之后我從來不會急著做下一道而是會花十分鐘做三件事第一把題解里最優(yōu)解法的思路不看代碼地重新寫一遍第二把這個解法的時間空間復(fù)雜度寫在題目標(biāo)題旁邊第三想想如果題目條件變了比如要求返回所有下標(biāo)、要求不能用額外空間、要求數(shù)組有序解法會不會變化會怎么變化。這個習(xí)慣讓我在刷到第 200 題左右的時候明顯感覺到套路感增強(qiáng)了。很多題看一眼大概率知道用哈希表還是雙指針還是貪心不是因?yàn)橛浟舜鸢付且驗(yàn)槊恳淮螐?fù)盤都在強(qiáng)化思路的連接。兩數(shù)之和是第一題也是很多 C 同學(xué)進(jìn)入算法世界的第一個入口。希望這篇拆解能幫你把這道題理解得比“背答案”更透一點(diǎn)。把第一個臺階踩穩(wěn)了后面的樓梯就好走了。 兩數(shù)之和C++解法拆解：從暴力枚舉到哈希表優(yōu)化
兩數(shù)之和這道題在力扣平臺上的編號是第一題路徑是“力扣——1”也是絕大多數(shù)人打開刷題生涯的那扇門。它本身并不難但作為C入門選手第一道題往往決定了你后續(xù)刷題的姿勢和手感所以我一直覺得有必要把它拆透了講。這篇不說廢話直接圍繞題面、三種層級的解法演進(jìn)、C代碼逐行實(shí)現(xiàn)、本地環(huán)境配置、常見坑點(diǎn)展開把這道題吃干抹凈。1. 題面與核心需求拆解1.1 題目到底在問什么原題是這樣的給定一個整數(shù)數(shù)組nums和一個整數(shù)目標(biāo)值target請在數(shù)組中找出和為目標(biāo)值target的那兩個整數(shù)并返回它們的數(shù)組下標(biāo)。示例輸入nums [2,7,11,15], target 9 輸出[0,1] 解釋因?yàn)?nums[0] nums[1] 9返回 [0, 1]注意這里問的不是“值”而是“下標(biāo)”。很多人第一次做的時候答案對了但輸出的是數(shù)組元素本身結(jié)果直接判錯。力扣要求返回的是vectorint里面裝的是兩個索引這個細(xì)節(jié)必須盯死。題目還給了兩個隱含保證一是每種輸入只會對應(yīng)一個答案這意味著你不用處理“多組答案”的情況看到一組配直接返回就行二是數(shù)組中同一個元素不能使用兩遍。這句話很多人沒讀懂我解釋一下它不是說你不能選兩個相同的值而是說一個下標(biāo)不能用兩次。比如nums [3, 3]target 6是合法輸入答案是[0, 1]兩個3是不同的下標(biāo)但如果你拿著同一個下標(biāo)算兩次比如nums[i] nums[i]那是被禁止的。1.2 從題面里挖出的約束條件這道題的輸入規(guī)模在力扣上現(xiàn)在已經(jīng)加強(qiáng)過了數(shù)組長度最多能到10^4甚至10^5級別。這意味著什么意味著 O(n^2) 的暴力解在最壞情況下要做大約 10^8 到 10^10 次操作放到老版本的數(shù)據(jù)上也許能蒙混過關(guān)放到現(xiàn)在的評測數(shù)據(jù)里基本會超時。目標(biāo)值target和數(shù)組元素都是整數(shù)可正可負(fù)不排除有負(fù)數(shù)的情況。很多人拿到題目就默認(rèn)所有數(shù)都是正的結(jié)果測試一跑就掛在負(fù)數(shù)用例上。實(shí)際上target - nums[i]完全可能是負(fù)數(shù)這不影響哈希表的查找但會影響你自己手寫“剪枝”之類的優(yōu)化時的心態(tài)。還有一個隱含信息返回值順序沒有要求你可以返回[0, 1]也可以返回[1, 0]。這個自由度給了哈希表解法一定的容錯空間也讓我們在實(shí)現(xiàn)時不用糾結(jié)先存誰后取誰。2. 解法演進(jìn)從暴力到哈希表2.1 暴力枚舉最直覺但最容易超時的方案很多人的第一反應(yīng)是兩層循環(huán)掃描外層固定一個數(shù)內(nèi)層從它后面找配對的數(shù)。代碼大概長這樣class Solution { public: vectorint twoSum(vectorint nums, int target) { int n nums.size(); for (int i 0; i n; i) { for (int j i 1; j n; j) { if (nums[i] nums[j] target) { return {i, j}; } } } return {}; } };這個方案的時間復(fù)雜度是 O(n^2)空間復(fù)雜度 O(1)。它簡單、直觀、不容易錯但有一個致命問題數(shù)組一大就歇菜。力扣現(xiàn)在的數(shù)據(jù)規(guī)模下n 10^5時n^2就是 10^10哪怕每次比較只消耗幾個時鐘周期整體也要幾十秒量級評測系統(tǒng)直接判超時。我見過不少初學(xué)者死磕暴力解提交超時后一臉茫然其實(shí)這里需要的不是“更快的暴力”而是換一種查找思路。暴力解慢的根本原因是內(nèi)層循環(huán)每次都在線性掃描判斷“有沒有一個數(shù)等于 target - nums[i]”這件事花費(fèi)了 O(n) 的時間。如果我們把“查找某個值是否存在”的時間從 O(n) 降到 O(1)總復(fù)雜度自然就下來了。2.2 哈希表用空間換時間的經(jīng)典思路哈希表或者說 C 里的unordered_map干的事情就是把值映射到它的位置。你可以理解為它給所有數(shù)字建了一張“索引表”每次想找某個數(shù)有沒有出現(xiàn)過按鍵查一下就行平均只需 O(1) 時間?；谶@個思路算法變成遍歷數(shù)組每到一個元素nums[i]先算complement target - nums[i]去哈希表里查這個complement是否存在存在說明之前已經(jīng)遍歷到過這個數(shù)直接返回它對應(yīng)的下標(biāo)和當(dāng)前下標(biāo)i不存在就把nums[i]和它的下標(biāo)i存進(jìn)哈希表繼續(xù)遍歷。這里的關(guān)鍵是先查后存順序不能亂。原因后面在避坑部分會詳細(xì)說這里先記住這個原則。2.3 為什么一次遍歷就夠很多人對“一次遍歷”感到不踏實(shí)總覺得得先把全部元素放進(jìn)哈希表再從頭查一遍才能保證找全。其實(shí)大可不必。舉個例子nums [2, 7, 11, 15]target 9。遍歷到2的時候complement 7哈希表里沒有 7于是把2 - 0存進(jìn)去遍歷到7的時候complement 2一查哈希表2在 0 號位存著呢直接返回[0, 1]。你發(fā)現(xiàn)沒有當(dāng)你遍歷到任何一個元素的時候它前面的所有元素都已經(jīng)入表了。如果配對的數(shù)是它前面的某一個那么一定能查到如果配對的數(shù)在它后面那現(xiàn)在是查不到的但等遍歷到后面那個數(shù)的時候當(dāng)前元素已經(jīng)入表到時照樣能查到。所以一次遍歷就夠了不存在漏掉的情況。這個“一邊查一邊存”的模式在力扣里大量出現(xiàn)比如后面會遇到的三數(shù)之和、兩數(shù)之和系列變體本質(zhì)上都是這個套路。把第一題的哈希思維吃透后面會輕松很多。3. C代碼的逐行實(shí)現(xiàn)與細(xì)節(jié)3.1 完整代碼和提交模板我們直接上最終版本這是我在本地和力扣上都驗(yàn)證過的寫法#include vector #include unordered_map class Solution { public: vectorint twoSum(vectorint nums, int target) { unordered_mapint, int hash; // 值 - 下標(biāo) for (int i 0; i nums.size(); i) { int complement target - nums[i]; auto it hash.find(complement); if (it ! hash.end()) { return {it-second, i}; } hash[nums[i]] i; } return {}; } };在力扣的提交環(huán)境里vector和unordered_map的頭文件已經(jīng)默認(rèn)包含所以很多題解里不會寫#include。但你在本地跑的時候必須自己補(bǔ)上否則編譯直接報錯。我建議即使是在力扣頁面寫代碼也養(yǎng)成把頭文件寫全的習(xí)慣這樣切到本地調(diào)試的時候不用額外改。這里有幾個C的點(diǎn)需要解釋一下尤其是新手容易卡住的地方。3.2 為什么用 unordered_map 而不是 mapC 標(biāo)準(zhǔn)庫里有兩個容器都能做鍵值映射一個是map底層是紅黑樹插入查找都是 O(log n) 的另一個是unordered_map底層是哈希表插入查找平均 O(1)。這道題只要求“能不能快速找到某個值”不要求按順序遍歷鍵。所以選擇unordered_map是更合適的它在n較大時優(yōu)勢明顯。map雖然也能通過但 O(log n) 和 O(1) 在數(shù)據(jù)量大的時候差距會體現(xiàn)出來。還有一個隱藏區(qū)別是頭文件不同unordered_map需要#include unordered_mapmap需要#include map。別搞混。3.3 返回值與邊界處理函數(shù)簽名是vectorint twoSum(vectorint nums, int target)返回類型是vectorint。所以我們返回的時候可以用花括號初始化列表return {it-second, i};這個寫法是 C11 之后支持的本質(zhì)上是用initializer_list構(gòu)造一個臨時vector并返回。如果你用的是更老的編譯器標(biāo)準(zhǔn)可能會報錯所以本地編譯的時候我建議至少開-stdc11我個人習(xí)慣直接用 C17。至于最末尾的return {};其實(shí)是返回一個空 vector。正常情況下不會執(zhí)行到這里因?yàn)轭}目保證有且只有一個答案但這行代碼能讓編譯器滿意覆蓋掉“函數(shù)可能沒有返回值”的告警。有些強(qiáng)迫癥可能會直接寫return {-1, -1};或者return {0, 0};也行不影響正確性就是語義上不如空 vector 干凈。再強(qiáng)調(diào)一下auto it hash.find(complement)。find返回的是一個迭代器類型寫全了是unordered_mapint, int::iterator太長了用auto省心。判斷是否存在就看它是否等于hash.end()。這里新手最容易犯的錯是直接寫hash[complement]結(jié)果查一個不存在的鍵時operator[]會悄悄把這個鍵插入并賦默認(rèn)值 0導(dǎo)致下標(biāo)返回 0邏輯直接搞亂。記住查用find插用operator[]或insert不要拿operator[]干查找的活。4. 實(shí)操過程從本地環(huán)境到提交通過4.1 把 VSCode 調(diào)成刷題順手的環(huán)境力扣網(wǎng)頁端可以直接寫代碼提交但很多人還是喜歡在本地跑。原因很簡單本地能斷點(diǎn)調(diào)試、能加打印、能反復(fù)實(shí)驗(yàn)比在網(wǎng)頁端看著報錯干瞪眼強(qiáng)太多。雖然題目寫完了都能通過但調(diào)試的過程才是真正學(xué)到東西的過程。我用的是 VSCode配合 C/C 擴(kuò)展配置一次之后刷題非常順手。你需要準(zhǔn)備VSCode一個 C 編譯器Windows 上可以用 MinGW-w64 或者 MSVCmacOS 上可以用 Xcode Command Line Tools 自帶的 clangC/C 擴(kuò)展編譯器安裝完之后在終端里輸入g --version能輸出版本號就說明環(huán)境沒問題。然后要創(chuàng)建一個tasks.json負(fù)責(zé)編譯。我通常的做法是給刷題建一個單獨(dú)的目錄比如leetcode里面每個題一個文件夾第1題就在0001_two_sum下放一個main.cpp。main.cpp里除了放Solution類再寫一個簡單的測試main函數(shù)把示例和邊界用例都跑一遍int main() { Solution sol; vectorint nums1 {2, 7, 11, 15}; vectorint res1 sol.twoSum(nums1, 9); for (int x : res1) cout x ; // 輸出 0 1 cout endl; vectorint nums2 {3, 3}; vectorint res2 sol.twoSum(nums2, 6); for (int x : res2) cout x ; // 輸出 0 1 cout endl; vectorint nums3 {-3, 4, 3, 90}; vectorint res3 sol.twoSum(nums3, 0); for (int x : res3) cout x ; // 輸出 0 2 cout endl; return 0; }至于編譯運(yùn)行為什么不直接在終端敲命令其實(shí)可以敲但不是每個人都想背一長串g -stdc17 main.cpp -o main。配置好tasks.json之后按CtrlShiftB就能一鍵編譯再按 F5 就能啟動調(diào)試。VSCode 的launch.json里把externalConsole或者internalConsole配好命中斷點(diǎn)之后能清清楚楚看到hash表里存了什么值、complement是多少、迭代器指向哪里。這個調(diào)試過程對新手尤其有幫助。我自己刷題前兩年相當(dāng)一部分容易混淆的概念比如迭代器失效、引用傳參、返回值優(yōu)化都是在斷點(diǎn)面板里反復(fù)看出來的。4.2 關(guān)鍵的調(diào)試用例設(shè)計很多人刷題只跑一遍示例就提交過了就算數(shù)沒過就干瞪眼。稍微好一點(diǎn)的做法是準(zhǔn)備幾組典型的測試數(shù)據(jù)每組數(shù)據(jù)都帶著不同的邊界含義。這道題我建議至少準(zhǔn)備四組測試用例target期望結(jié)果驗(yàn)證點(diǎn)[2, 7, 11, 15]9[0, 1]官方示例標(biāo)準(zhǔn)情況[3, 3]6[0, 1]兩個相同數(shù)值不同下標(biāo)[-3, 4, 3, 90]0[0, 2]存在負(fù)數(shù)target減完為負(fù)[1]2空數(shù)組過短題目不會出現(xiàn)但代碼要兜底第一組測的是最基本的功能第二組測的是“同一元素不能使用兩遍”這個約束是否被正確處理第三組測的是負(fù)數(shù)鍵在unordered_map里能否正常索引第四組是防御性測試雖然題目保證一定有答案但萬一你代碼里存在空指針或者越界風(fēng)險這組能幫你提前暴露。4.3 如果一切順利提交時還有什么要檢查本地跑通了之后去力扣頁面上提交有幾點(diǎn)容易忽略第一提交的時候類名和函數(shù)簽名必須和題目完全一致大小寫、參數(shù)類型、返回類型都不能改。力扣的評測系統(tǒng)是拿固定的測試代碼調(diào)用你的Solution::twoSum你改了簽名就編譯不過。第二返回值順序沒有要求但有些同學(xué)本地測試時自己用vectorint比較結(jié)果嚴(yán)格匹配[0, 1]由于題目允許[1, 0]這種比較方式并不嚴(yán)謹(jǐn)。如果你想寫自動化驗(yàn)證最好把結(jié)果排序后再比較或者用set存下兩個值再比對。第三提交前把頭文件相關(guān)的#include刪掉其實(shí)不影響因?yàn)榱郗h(huán)境自動包含了。但如果你連std::前綴都省了可能會導(dǎo)致命名沖突。穩(wěn)妥起見全部按標(biāo)準(zhǔn)寫法來。5. 常見問題與避坑實(shí)錄5.1 最容易踩的幾個坑第一個坑把整個數(shù)組先塞進(jìn)哈希表再開始查找。這個做法錯在哪看這個用例nums [3, 3]target 6。如果你第一步把整個數(shù)組遍歷一遍存進(jìn)哈希表因?yàn)殒I是值、值是下標(biāo)兩個 3 的鍵相同后面的下標(biāo)會把前面的覆蓋掉最終hash[3] 1。然后你從頭再來一遍遍歷到下標(biāo) 0 時complement 3一查哈希表發(fā)現(xiàn) 3 存在返回的答案是[1, 0]。這道題答案允許任意順序所以這個用例僥幸通過了。但換個場景nums [3, 2, 3]target 6同樣先塞后查最終hash[3] 2遍歷到下標(biāo) 0 時返回[2, 0]依然能通過?？雌饋砗孟窨偸悄芡ㄟ^但這不是因?yàn)檫壿嬚_而是因?yàn)槟愕闹当弧案采w成最后一個同值下標(biāo)”后碰巧仍滿足題目“返回任意順序”的要求?？梢坏╊}目改成“下標(biāo)也必須按原順序返回”或者存在多個同值元素時這個覆蓋就會造成錯誤。所以規(guī)范的做法永遠(yuǎn)是“先查再存”這不僅是性能問題更是邏輯嚴(yán)謹(jǐn)性的問題。第二個坑用hash[complement]判斷鍵是否存在。我上面提過operator[]在鍵不存在時會自動插入默認(rèn)值 0。假設(shè)nums [2, 7]target 9這種簡單例子第一次循環(huán)查complement 7不存在hash[7]會被插入一個值為 0 的條目。第二次循環(huán)查到 2它返回的哈希表值是 0恰好是正確下標(biāo)所以你誤以為代碼沒問題。但假如complement的值在數(shù)組里根本不存在hash[complement]會返回 0讓你誤以為下標(biāo) 0 就是答案直接返回了錯誤的[0, i]。這就是為什么必須用find實(shí)在要用count也可以但不要直接用operator[]查。第三個坑返回下標(biāo)時把順序?qū)懛础Ｕ_邏輯是complement存在哈希表里it-second是配對值之前入表時的下標(biāo)i是當(dāng)前下標(biāo)。有些同學(xué)邏輯跑通后下意識寫成return {i, it-second}測試用例里如果兩個下標(biāo)恰好是對稱的可能也能通過但一旦順序反了且測試用例要求特定順序就會掛。這道題不要求順序但為了養(yǎng)成好習(xí)慣還是按照“先查到的放前面當(dāng)前的放后面”來寫。第四個坑認(rèn)為nums.size()的返回值可以直接拿來當(dāng)int用。size()返回的是size_t在 64 位系統(tǒng)上是unsigned long long。刷題時基本不會出問題但如果你寫for (int i 0; i nums.size(); i)編譯器會有符號比較的告警。我一般直接寫int n nums.size();后再用n循環(huán)或者用size_t i。5.2 話不多說關(guān)聯(lián)擴(kuò)展題該往哪走兩數(shù)之和只是一系列問題的起點(diǎn)。刷完這道題你最應(yīng)該趁熱打鐵做以下幾類力扣 167兩數(shù)之和 II - 輸入有序數(shù)組。同樣是兩數(shù)之和但數(shù)組有序可以用雙指針做到 O(1) 空間這和哈希表解法思路完全不同。力扣 15三數(shù)之和。把“兩個數(shù)的和”擴(kuò)展成“三個數(shù)和為0”核心思路是先排序再雙指針哈希表的地位被削弱了。力扣 121買股票的最佳時機(jī)。這個題不是兩數(shù)之和的變體但同樣是“一次遍歷維護(hù)狀態(tài)”的經(jīng)典場景和哈希表的“邊查邊存”有異曲同工之處。我一直覺得刷題不能只滿足于 AC 一道題。把一道題吃透再沿著它的變體往下走整個知識網(wǎng)絡(luò)就串起來了。兩數(shù)之和背后那個“查找表”的抽象其實(shí)在真實(shí)開發(fā)中也經(jīng)常用到比如緩存鍵值對、去重、索引構(gòu)建本質(zhì)都是哈希表的應(yīng)用。6. 一點(diǎn)私貨我的刷題習(xí)慣說了這么多最后分享一個我自己的習(xí)慣。每次 AC 之后我從來不會急著做下一道而是會花十分鐘做三件事第一把題解里最優(yōu)解法的思路不看代碼地重新寫一遍第二把這個解法的時間空間復(fù)雜度寫在題目標(biāo)題旁邊第三想想如果題目條件變了比如要求返回所有下標(biāo)、要求不能用額外空間、要求數(shù)組有序解法會不會變化會怎么變化。這個習(xí)慣讓我在刷到第 200 題左右的時候明顯感覺到套路感增強(qiáng)了。很多題看一眼大概率知道用哈希表還是雙指針還是貪心不是因?yàn)橛浟舜鸢付且驗(yàn)槊恳淮螐?fù)盤都在強(qiáng)化思路的連接。兩數(shù)之和是第一題也是很多 C 同學(xué)進(jìn)入算法世界的第一個入口。希望這篇拆解能幫你把這道題理解得比“背答案”更透一點(diǎn)。把第一個臺階踩穩(wěn)了后面的樓梯就好走了。