很多人打開力扣 hot100第一眼看到的就是「兩數(shù)之和」。我見過不少同學(xué)覺得這題太簡(jiǎn)單掃一眼就關(guān)了也見過更多人背下了哈希表的答案卻講不出為什么這么寫。這道題在力扣 hot100 里的位置太特殊了——它幾乎是所有 Java 面試者刷題之路的第一站也是很多面試官三分鐘熱身時(shí)最常用的題。但恰恰是這道看起來最簡(jiǎn)單的題最能暴露一個(gè)人的基本功HashMap 用的熟不熟、復(fù)雜度會(huì)不會(huì)算、邊界情況想不想得全、代碼風(fēng)格干不干凈。這篇文章我想認(rèn)真聊聊兩數(shù)之和這道題尤其是 Java 版本的完整解法。不會(huì)只丟一個(gè)最優(yōu)解代碼就完事而是從暴力解開始推演一步步走到哈希表方案再把里面容易踩的坑、面試官的追問、以及從這道題延伸出去的一類題都梳理清楚。無論你是剛準(zhǔn)備刷題的新手還是想把 hot100 吃透的求職者這篇都值得你花十分鐘讀完。1. 題目到底在考什么先看懂兩數(shù)之和的本質(zhì)1.1 把題目翻譯成人話原題描述很簡(jiǎn)潔給定一個(gè)整數(shù)數(shù)組nums和一個(gè)整數(shù)目標(biāo)值target請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那兩個(gè)整數(shù)并返回它們的數(shù)組下標(biāo)。你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案并且你不能使用兩次相同的元素。這幾句話里有幾個(gè)關(guān)鍵約束必須讀出來。第一返回的是下標(biāo)不是值本身這意味著解題時(shí)得跟著下標(biāo)走。第二每種輸入只會(huì)有一個(gè)答案所以不需要處理多解的情況找到一個(gè)就可以返回。第三同一個(gè)元素不能用兩次這個(gè)約束在實(shí)現(xiàn)時(shí)常常被忽略后面我會(huì)專門講它是怎么坑人的。1.2 從生活場(chǎng)景理解「查找配對(duì)」問題我習(xí)慣把這題理解成在書店里找兩本書。假設(shè)書架上每本書都有自己的編號(hào)你要找兩本編號(hào)加起來恰好等于某個(gè)數(shù)字的書。最笨的辦法就是拿起第一本然后挨個(gè)往后翻其他書看編號(hào)能不能湊上翻完一輪沒找到再拿起第二本再從頭翻一遍。這就是暴力解。那聰明一點(diǎn)的做法是什么你一邊翻書一邊在手上的小本子上記錄書編號(hào)是多少放在第幾個(gè)位置。之后每翻到一本新書你只需要查一下小本子上有沒有一本書編號(hào)等于目標(biāo)值減去當(dāng)前這本的編號(hào)。有的話直接去對(duì)應(yīng)位置拿書沒有的話就把當(dāng)前這本登記進(jìn)小本子繼續(xù)翻下一本。這個(gè)小本子在程序里就是哈希表。1.3 為什么 hot100 把它放在第一題力扣 hot100 是從海量題目里篩出來的高頻面試題集合覆蓋了大多數(shù)面試?？嫉乃惴ê蛿?shù)據(jù)結(jié)構(gòu)。兩數(shù)之和作為整個(gè)列表的第一題并不是因?yàn)樗y而是因?yàn)樗欠浅：玫摹笖?shù)據(jù)結(jié)構(gòu)入門題」。它用最小的代碼量完整展示了從 O(n^2) 到 O(n) 的優(yōu)化過程涉及了哈希表這個(gè)面試最高頻的數(shù)據(jù)結(jié)構(gòu)還天然能延伸出雙指針、排序、去重等一系列后續(xù)考點(diǎn)。算是用最簡(jiǎn)單的外殼裝了最核心的面試知識(shí)點(diǎn)。2. 暴力解為什么能過但千萬別止步于「能過」2.1 兩層循環(huán)的樸素寫法先看大部分人第一直覺寫出來的代碼public int[] twoSum(int[] nums, int target) { int n nums.length; for (int i 0; i n; i) { for (int j i 1; j n; j) { if (nums[i] nums[j] target) { return new int[]{i, j}; } } } return new int[0]; }這段代碼在力扣上是能通過的因?yàn)轭}目給的數(shù)據(jù)范圍不大O(n^2) 的復(fù)雜度在 n 只有幾百、幾千的時(shí)候完全跑得動(dòng)。我見過很多初學(xué)者刷到這里就覺得自己搞定了這恰恰是最危險(xiǎn)的錯(cuò)覺。2.2 暴力解的復(fù)雜度到底有多高來分析一下這段代碼的時(shí)間復(fù)雜度。外層循環(huán)跑 n 次內(nèi)層循環(huán)平均跑 n/2 次總的比較次數(shù)是 n*(n-1)/2量級(jí)就是 O(n^2)?？臻g復(fù)雜度是 O(1)除了幾個(gè)臨時(shí)變量沒有額外開銷。O(n^2) 在數(shù)據(jù)量小的時(shí)候感覺不出來但你把 n 從 1000 提到 100000計(jì)算量就差了大約一百倍。真實(shí)的工程場(chǎng)景里接口請(qǐng)求動(dòng)輒幾萬幾十萬的數(shù)據(jù)量沒人能接受這種復(fù)雜度。面試官讓你寫兩數(shù)之和最終想看到的一定是 O(n) 的解法。2.3 暴力解真正的學(xué)習(xí)價(jià)值暴力解不是沒有價(jià)值它的價(jià)值在于幫你建立「基線」。我們分析一個(gè)算法題第一步永遠(yuǎn)是先想最暴力的做法確認(rèn)它能解決這個(gè)問題再去優(yōu)化。暴力解提供了一個(gè)正確性基準(zhǔn)后面你寫了任何優(yōu)化版本都可以拿它來驗(yàn)證結(jié)果對(duì)不對(duì)。另外暴力解里有個(gè)細(xì)節(jié)值得提一下內(nèi)層循環(huán)從j i 1開始而不是從 0 開始。這樣既避免了同一個(gè)元素自己和自己的組合也避免了一對(duì)元素被重復(fù)計(jì)算兩次。這個(gè)寫代碼的直覺后續(xù)做很多數(shù)組問題都用得上。3. 哈希表解法從「找人」到「登記簿」的思路轉(zhuǎn)換3.1 核心推理把查找從 O(n) 降到 O(1)暴力解慢在哪里慢在每次都要掃描整個(gè)數(shù)組去找target - nums[i]是否存在的這個(gè)過程。數(shù)組是一個(gè)無序的存儲(chǔ)結(jié)構(gòu)查找一個(gè)元素只能逐個(gè)遍歷這就是 O(n) 的來源。有沒有一種數(shù)據(jù)結(jié)構(gòu)能讓我以 O(1) 的代價(jià)查到一個(gè)元素是否存在并且拿到它的下標(biāo)有就是哈希表。Java 里對(duì)應(yīng)的是HashMap。哈希表內(nèi)部通過哈希函數(shù)把 key 映射到數(shù)組桶位上所以查找的平均時(shí)間復(fù)雜度是 O(1)。于是思路就變成了遍歷數(shù)組的過程中維護(hù)一個(gè) HashMapkey 存「已經(jīng)出現(xiàn)過的元素值」value 存「這個(gè)元素的下標(biāo)」。每次遇到一個(gè)新元素nums[i]先查一下target - nums[i]是不是已經(jīng)在 map 里了。如果在那答案就找到了如果不在把當(dāng)前元素放進(jìn)去繼續(xù)遍歷。3.2 為什么一定是 HashMap 而不是 HashSet很多新手會(huì)混淆這兩個(gè)結(jié)構(gòu)。HashSet 只能判斷「某個(gè)值是否存在」但它拿不到下標(biāo)。而這題要返回的是下標(biāo)所以必須有 value 來存下標(biāo)信息。HashMap 的 key 存值、value 存下標(biāo)完美匹配需求。這里有一個(gè)值得記住的做題思維題目要求返回什么數(shù)據(jù)結(jié)構(gòu)就存什么。返回下標(biāo)就存下標(biāo)返回所有組合就把組合存成 List返回?cái)?shù)量就直接計(jì)數(shù)。先明確輸出再設(shè)計(jì)存儲(chǔ)。3.3 為什么必須邊遍歷邊放而不能先全部放進(jìn)去這是整道題里最容易踩的坑我面試別人的時(shí)候也常用這個(gè)點(diǎn)來區(qū)分候選人是不是真的理解了哈希表解法。錯(cuò)誤寫法是這樣的先遍歷一遍數(shù)組把所有元素放進(jìn) map再遍歷一遍檢查target - nums[i]是否在 map 里?？雌饋頉]毛病但碰到重復(fù)元素就出問題了。比如nums [3, 3]target 6。如果你先把所有元素放進(jìn)去map 中 key3 的 value 會(huì)被第二次放入的 3 覆蓋成下標(biāo) 1。然后遍歷第一個(gè)下標(biāo) 0 時(shí)查target - nums[0] 3發(fā)現(xiàn) map 里有返回[0, 1]——看起來碰巧對(duì)了。但如果題目稍微改一下比如nums [3, 3]但你遍歷到下標(biāo) 1 才去查就會(huì)返回[1, 1]這就不對(duì)了因?yàn)橥粋€(gè)元素不能被用兩次。邊遍歷邊放就天然規(guī)避了這個(gè)問題。因?yàn)楫?dāng)你站在下標(biāo) i 時(shí)map 里只存了下標(biāo) 0 到 i-1 的元素永遠(yuǎn)不會(huì)用當(dāng)前這個(gè)元素匹配自己。正確的核心邏輯MapInteger, Integer map new HashMap(); for (int i 0; i nums.length; i) { int complement target - nums[i]; if (map.containsKey(complement)) { return new int[]{map.get(complement), i}; } map.put(nums[i], i); }4. Java 實(shí)現(xiàn)的細(xì)節(jié)打磨一份能拿高分的完整答案4.1 完整參考代碼帶注釋與邊界處理一個(gè)能拿高分的解答不只是把核心邏輯寫出來還要有清晰的命名、合理的邊界處理、和良好的代碼習(xí)慣。我一般會(huì)這樣寫public int[] twoSum(int[] nums, int target) { // 邊界情況數(shù)組為空或長(zhǎng)度小于2直接返回空數(shù)組 if (nums null || nums.length 2) { return new int[0]; } // key為數(shù)組元素值value為元素下標(biāo) MapInteger, Integer numIndexMap new HashMap(); for (int i 0; i nums.length; i) { int complement target - nums[i]; // 已經(jīng)遍歷過的部分中是否存在需要的差值 if (numIndexMap.containsKey(complement)) { return new int[]{numIndexMap.get(complement), i}; } // 不存在則記錄當(dāng)前值的位置繼續(xù)遍歷 numIndexMap.put(nums[i], i); } // 按題設(shè)不會(huì)走到這一步但保留兜底返回 return new int[0]; }這段代碼的時(shí)間復(fù)雜度為 O(n)因?yàn)橐淮伪闅v每次 map 操作平均 O(1)空間復(fù)雜度為 O(n)因?yàn)樽顗那闆r下需要把 n 個(gè)元素都放進(jìn) map。這個(gè) trade-off 在面試時(shí)要主動(dòng)講清楚用 O(n) 的空間換來了 O(n) 的時(shí)間。4.2 從暴力到哈希代碼是怎么一步步演化的我建議初學(xué)者在草稿紙上先寫出暴力解確認(rèn)正確性然后思考這樣一個(gè)問題暴力解里最耗時(shí)的部分是什么是內(nèi)層循環(huán)的查找。能不能讓查找更快如果能用一個(gè) map 把所有見過的值存下來每次直接查是不是就不需要那個(gè)內(nèi)層循環(huán)了帶著這個(gè)思路去寫優(yōu)化版邏輯是水到渠成的。不要一上來就背哈希表的答案。你自己推一遍暴力到哈希的演化過程面試官問「為什么用哈希表」的時(shí)候你才能從原理上講清楚而不是只能說「大家都這么寫」。4.3 易錯(cuò)點(diǎn)對(duì)照這幾處寫錯(cuò)的人最多我整理了幾個(gè) Java 實(shí)現(xiàn)里常見的容易寫錯(cuò)的地方對(duì)照如下易錯(cuò)點(diǎn)錯(cuò)誤示例正確做法原因數(shù)組空指針直接訪問 nums.length先判 null 再取 length工程習(xí)慣防止 NPE返回空數(shù)組return nullreturn new int[0]返回空數(shù)組比 null 更安全元素自己匹配自己先全部放入 map 再查邊查邊放避免同一元素被使用兩次重復(fù) key 覆蓋使用 put 多次導(dǎo)致 value 被覆蓋先 containsKey 再?zèng)Q定是否放入保證存的是最早出現(xiàn)的下標(biāo)返回順序不統(tǒng)一有時(shí)先 i 后 map有時(shí)反過來統(tǒng)一先 map 下標(biāo)再當(dāng)前下標(biāo)保持代碼穩(wěn)定可讀4.4 關(guān)于 getOrDefault 的一段補(bǔ)充有些同學(xué)會(huì)看到getOrDefault的寫法覺得更簡(jiǎn)潔。比如Integer preIndex map.getOrDefault(target - nums[i], -1); if (preIndex ! -1) { return new int[]{preIndex, i}; }這種寫法功能上沒問題但有一個(gè)隱患如果數(shù)組中存在下標(biāo)為 -1 的合法情況數(shù)組下標(biāo)確實(shí)是非負(fù)的所以實(shí)際不會(huì)語義上就不干凈。更重要的是當(dāng)差值不存在時(shí)返回 -1你還得區(qū)分「不存在」和「下標(biāo)真的為 0」這兩種情況。雖然在這道題里用 -1 作為哨兵是安全的但從代碼可讀性角度我更推薦containsKeyget的顯式寫法讓人一眼看懂邏輯。5. 面試官常在兩數(shù)之和后面埋的追問5.1 如果數(shù)組是有序的能不能優(yōu)化空間這道題最常見的變體是給定一個(gè)升序排列的數(shù)組找出兩個(gè)數(shù)使它們的和等于 target返回它們的下標(biāo)。數(shù)組有序時(shí)可以用雙指針對(duì)撞法。一個(gè)指針指向數(shù)組頭部一個(gè)指向尾部計(jì)算兩數(shù)之和。和太大了右指針左移和太小了左指針右移找到相等就返回。這個(gè)過程的時(shí)間復(fù)雜度是 O(n)空間復(fù)雜度 O(1)比哈希表更省空間。但要注意原題的兩數(shù)之和返回的是原始下標(biāo)如果你先對(duì)數(shù)組排序下標(biāo)就亂了。所以面試?yán)镉龅健赣行驍?shù)組 返回下標(biāo)」的組合需要先把原數(shù)組轉(zhuǎn)成一個(gè)包含值和原始下標(biāo)的 Pair 數(shù)組排序時(shí)帶著下標(biāo)一起走再用雙指針。如果只要求返回值那直接對(duì)原數(shù)組排序加雙指針就行。5.2 如果要求返回所有不重復(fù)的解而不是一個(gè)解這個(gè)變體直接通向三數(shù)之和、四數(shù)之和。典型的做法是先排序然后固定一個(gè)數(shù)剩下的部分用雙指針找兩數(shù)之和同時(shí)跳過重復(fù)元素避免產(chǎn)生重復(fù)解。// 偽代碼思路排序后固定 i雙指針找兩數(shù) Arrays.sort(nums); for (int i 0; i n - 2; i) { if (i 0 nums[i] nums[i - 1]) continue; int left i 1, right n - 1; while (left right) { int sum nums[i] nums[left] nums[right]; if (sum target) { // 記錄結(jié)果然后去重移動(dòng)雙指針 } else if (sum target) { left; } else { right--; } } }5.3 如果數(shù)組非常大內(nèi)存裝不下哈希表怎么辦這是一個(gè)典型的工程擴(kuò)展問題。這時(shí)候要考慮的不是單機(jī)內(nèi)存解法而是能否把問題拆到多臺(tái)機(jī)器并行處理或者利用外部排序后分段處理甚至如果數(shù)據(jù)分布有規(guī)律可以先判斷 target 的范圍縮小候選數(shù)據(jù)。這類問題沒有標(biāo)準(zhǔn)答案面試官考察的是你有沒有處理大數(shù)據(jù)的意識(shí)。5.4 兩數(shù)之和是 nSum 問題的地基兩數(shù)之和最簡(jiǎn)單的版本其實(shí)是 value 版本給定數(shù)組和一個(gè) target判斷是否存在兩個(gè)數(shù)的和等于 target。在此基礎(chǔ)上可以一步步升級(jí)兩數(shù)之和返回下標(biāo)需要用 HashMap 存值到下標(biāo)的映射兩數(shù)之和返回所有不重復(fù)的值組合排序加雙指針去重三數(shù)之和固定一個(gè)數(shù)轉(zhuǎn)化為兩數(shù)之和四數(shù)之和固定兩個(gè)數(shù)再轉(zhuǎn)化為兩數(shù)之和把這個(gè)鏈條理解透比單獨(dú)背十道題有用得多。hot100 里面很大一部分題目都是這種層層遞進(jìn)的關(guān)系抓住主線學(xué)習(xí)效率會(huì)高很多。6. 刷 hot100 的正確節(jié)奏從一道題到一類題6.1 一道兩數(shù)之和能帶出哪些知識(shí)點(diǎn)我自己刷題有個(gè)習(xí)慣每道題做完之后不只記答案而是列一下這道題關(guān)聯(lián)的知識(shí)點(diǎn)清單。兩數(shù)之和的知識(shí)點(diǎn)清單大致是這樣的數(shù)據(jù)結(jié)構(gòu)HashMap 的查、插、覆蓋行為算法復(fù)雜度時(shí)間復(fù)雜度和空間復(fù)雜度的 trade-off雙指針?biāo)枷胗行驍?shù)組的 O(1) 空間解法排序與下標(biāo)保持Pair 排序、自定義比較器去重技巧排序后跳過相鄰重復(fù)元素邊界處理空數(shù)組、單元素?cái)?shù)組、無解情況每一個(gè)知識(shí)點(diǎn)都可以繼續(xù)展開。比如 HashMap 的 put 方法的返回值、containsKey 的時(shí)間復(fù)雜度、擴(kuò)容機(jī)制這些都是 Java 面試八股文里很常見的內(nèi)容。刷題和八股文不是對(duì)立的你完全可以在做這道題的時(shí)候順手把這些都復(fù)習(xí)了。6.2 我的刷題筆記模板我建議你給每道 hot100 題目建一個(gè)筆記包含四個(gè)部分題目一句話描述用自己的話說清楚題目要求暴力解思路與復(fù)雜度先寫最樸素的想法再分析慢在哪最優(yōu)解思路與復(fù)雜度記錄優(yōu)化過程而不是只寫最終答案易錯(cuò)點(diǎn)與延伸題把踩過的坑、面試官的追問寫下來兩數(shù)之和的筆記里我會(huì)特別標(biāo)注這次學(xué)到的核心經(jīng)驗(yàn)數(shù)組查找慢用哈希表換時(shí)間返回什么就存什么邊遍歷邊維護(hù)哈希表可以避免同一個(gè)元素用兩次。6.3 給剛開始刷 hot100 的人一個(gè)建議hot100 不是用來背的是用來建立算法思維的。前期不要追求每天刷很多題我反而建議一天只做一兩道但每道都把它吃透暴力解推導(dǎo)一遍最優(yōu)解推到一遍網(wǎng)上找一兩篇題解看看思路有什么不同再把相關(guān)變體題做一遍。這個(gè)過程比機(jī)械刷十道題有用得多。兩數(shù)之和作為第一題價(jià)值就在于此。它用最簡(jiǎn)單的方式讓你體驗(yàn)了完整的刷題方法論理解問題、暴力基線、結(jié)構(gòu)優(yōu)化、代碼實(shí)現(xiàn)、邊界處理、變體延伸。把這套方法論掌握住后面的 99 道題會(huì)順暢很多。我個(gè)人刷這道題已經(jīng)不下十遍了每次面試前還會(huì)翻出來看一眼。不是因?yàn)槲矣洸蛔〈鸢付敲看慰炊寄苡貌煌囊暯侨徱曀倪吔缛ヂ?lián)想新的題目。刷題這事的核心不在數(shù)量而在于你能否把一道經(jīng)典題背后承載的思維方式真正變成自己的東西。希望這篇兩數(shù)之和的完整梳理能幫你走好 hot100 的第一步。