LeetCode 884題名很長(zhǎng)Uncommon Words from Two Sentences中文一般翻譯成兩句話中的不常見單詞。第一次刷這題的人多半會(huì)覺得它簡(jiǎn)單給兩個(gè)句子把出現(xiàn)次數(shù)少的單詞找出來嘛?？晌以趯?shí)際提交前一度想用“集合差集”去解結(jié)果寫完才發(fā)現(xiàn)邏輯上有個(gè)洞最后老老實(shí)實(shí)回到哈希表詞頻統(tǒng)計(jì)。這道題雖然只是哈希計(jì)數(shù)的基礎(chǔ)應(yīng)用但它恰好卡在一個(gè)很經(jīng)典的直覺誤區(qū)上“只在一邊出現(xiàn)過”并不等于“兩邊都不常見”。這篇內(nèi)容適合三類讀者剛學(xué)完哈希表想找入門題鞏固的面試前快速過一遍字符串處理套路的以及想搞清楚“為什么這類題不能靠往下拆兩三個(gè)判斷條件硬寫”的人。題目本身沒有任何高端算法時(shí)間空間復(fù)雜度都是O(n)但它對(duì)“條件等價(jià)轉(zhuǎn)化”的要求非常典型值得拆開揉碎講一遍。我會(huì)從題面理解、反直覺反例、三種語言實(shí)現(xiàn)、邊界與復(fù)雜度、再到業(yè)務(wù)場(chǎng)景的映射完整過一遍我自己的解題思路和踩坑心得。1. 題面讀完先別急著寫代碼這道題到底在問什么1.1 原題輸入輸出速覽題目給兩個(gè)字符串句子s1和s2句子里的單詞都由小寫字母組成單詞之間用空格分隔。要求返回一個(gè)字符串?dāng)?shù)組數(shù)組里裝的是所有“不常見單詞”。什么算不常見原題的定義是這個(gè)單詞在恰好一個(gè)句子里出現(xiàn)且在這個(gè)句子里恰好出現(xiàn)一次。舉個(gè)例子s1 this apple is sweets2 this apple is sour輸出是[sweet, sour]。因?yàn)閠his、apple、is兩個(gè)句子都出現(xiàn)了不是不常見而sweet只在第一句出現(xiàn)一次sour只在第二句出現(xiàn)一次這兩個(gè)才能進(jìn)結(jié)果。再看另一個(gè)例子s1 apple apples2 banana。按直覺apple在第一句里出現(xiàn)了兩次所以它不算“恰好出現(xiàn)一次”不能輸出banana只出現(xiàn)一次可以輸出。結(jié)果為[banana]。這個(gè)例子很關(guān)鍵它直接把很多人的第一反應(yīng)打掉了僅僅保證“另一個(gè)句子沒有”是不夠的你自己的句子內(nèi)部也不能有重復(fù)。1.2 “只出現(xiàn)一次”到底限定在哪個(gè)集合我剛刷到這題時(shí)腦子里冒出來的第一句話是“找出只在一邊出的詞?！边@個(gè)說法很模糊因?yàn)椤爸辉谝贿叀笨梢杂兄辽賰煞N解讀解讀A這個(gè)單詞出現(xiàn)在s1中且不出現(xiàn)在s2中或出現(xiàn)在s2中且不出現(xiàn)在s1中。至于它在自己所在的句子里出現(xiàn)幾次不管。解讀B這個(gè)單詞在兩個(gè)句子中合計(jì)只出現(xiàn)一次。題目要的是解讀B。apple apple的例子能說明問題apple確實(shí)只在s1中出現(xiàn)、s2中沒有但它出現(xiàn)了兩次按解讀A也過不了“恰好出現(xiàn)一次”按解讀B同樣過不了。兩個(gè)解讀在這個(gè)例子上恰好結(jié)論一致真正區(qū)分它們的是更極端的場(chǎng)景s1 a bs2 a a b b。按解讀Aa和b都在兩個(gè)句子中出現(xiàn)了誰都不是“只在一邊”結(jié)果應(yīng)該為空按解讀Ba和b的總出現(xiàn)次數(shù)都大于1結(jié)果同樣為空?？雌饋磉€是一致。這兩者真正產(chǎn)生分歧的場(chǎng)景是一個(gè)單詞在自己句子中出現(xiàn)了兩次但另一邊完全沒有。比如s1 x xs2 y。解讀A會(huì)說x只在左邊出現(xiàn)算不常見解讀B會(huì)說x總共出現(xiàn)兩次不算。題目要的是解讀B。所以千萬不能把邏輯簡(jiǎn)化成“看單詞屬于哪邊的集合”而必須把“出現(xiàn)頻次”焊死在判斷條件里。1.3 一句等價(jià)的話讓解法直接定型把解讀B再翻譯一下一個(gè)單詞在兩個(gè)句子中合計(jì)出現(xiàn)次數(shù)恰好等于1。這個(gè)等價(jià)轉(zhuǎn)化是整個(gè)題的精髓。為什么它等價(jià)從定義出發(fā)一個(gè)不常見單詞必須滿足兩個(gè)條件在某個(gè)句子中恰好出現(xiàn)一次在另一個(gè)句子中完全沒出現(xiàn)。這本質(zhì)上說明它橫跨兩個(gè)句子的總次數(shù)就是1。反過來看如果某個(gè)單詞的總出現(xiàn)次數(shù)正好是1那么它不可能同時(shí)出現(xiàn)在兩個(gè)句子中也不可能在同一個(gè)句子中出現(xiàn)兩次它的唯一一次出現(xiàn)一定落在某一個(gè)句子里。因此“總頻次 1”和題目定義完全互相推出。一旦把這個(gè)等價(jià)關(guān)系寫出來解法就非常老套了把兩個(gè)句子的所有單詞合并成一個(gè)單詞流統(tǒng)計(jì)每個(gè)單詞的出現(xiàn)次數(shù)最后挑出計(jì)數(shù)等于1的那些單詞返回。整個(gè)過程和句子數(shù)量無關(guān)只和單詞流有關(guān)。這個(gè)轉(zhuǎn)化雖然簡(jiǎn)單但我覺得它才是本題真正的考點(diǎn)很多寫法繞來繞去寫一大堆if條件其實(shí)就是沒意識(shí)到這個(gè)等價(jià)關(guān)系。2. 為什么不能直接取兩句話的單詞差集2.1 集合操作丟掉頻數(shù)必翻車不少人的第一反應(yīng)是用集合把s1拆成一個(gè)Set把s2拆成一個(gè)Set然后對(duì)兩個(gè)集合做“對(duì)稱差集”——也就是(set1 - set2) (set2 - set1)把只在一邊出現(xiàn)的單詞收集起來。這套思路對(duì)“兩個(gè)句子各有一個(gè)相同單詞但這個(gè)單詞出現(xiàn)了兩次”的情況會(huì)直接失效。比如s1 b bs2 c c。兩個(gè)集合都是去重的結(jié)果set1 set2 {c}對(duì)稱差集是{b, c}于是錯(cuò)誤地返回兩個(gè)單詞。但按題目標(biāo)準(zhǔn)b在第一句出現(xiàn)了兩次c在第二句出現(xiàn)了兩次它們都不滿足“恰好出現(xiàn)一次”正確答案應(yīng)該是空數(shù)組。問題出在Set把“出現(xiàn)次數(shù)”這個(gè)信息揉碎了。集合只能回答“這個(gè)單詞存不存在”回答不了“它出現(xiàn)了幾遍”。而本題要求的“恰好出現(xiàn)一次”恰恰是頻數(shù)信息不是存在性信息。所以凡是用Set或“去重后取差集”的方案在出現(xiàn)同句重復(fù)詞的時(shí)候都會(huì)或多或少的出問題。2.2 兩個(gè) Map 分別計(jì)數(shù)可行但比合并計(jì)數(shù)更繞那有人會(huì)說“我不去重用兩個(gè)Map分別統(tǒng)計(jì)每個(gè)句子的詞頻然后遍歷的時(shí)候判斷freq1.get(w)1 !freq2.containsKey(w)反過來再處理一遍行不行”答案是可行的但非常容易出錯(cuò)。假設(shè)w在s1中出現(xiàn)一次在s2中也出現(xiàn)一次此時(shí)freq1.get(w)1且freq2.containsKey(w)true按上面的條件不會(huì)輸出沒毛病。但如果我寫的判斷條件是“freq1.get(w)1且freq2.getOrDefault(w,0)0”那是對(duì)的。問題就在于一旦條件寫復(fù)雜就很容易漏掉某條分支比如w在兩個(gè)句子中各自出現(xiàn)一次的情況有些人的直覺是“兩邊都出現(xiàn)肯定不常見”于是沒寫判斷結(jié)果倒是誤打誤撞對(duì)了。真正麻煩的是w在s1中出現(xiàn)兩次且s2中沒出現(xiàn)此時(shí)freq1.get(w)2第一個(gè)條件就不滿足正確跳過。這樣分兩個(gè)Map寫每個(gè)單詞要查兩次表還要考慮左右兩邊的對(duì)稱性代碼容易變得臃腫也更容易在邊界上失誤。合并成一個(gè)Map之后判斷條件從兩條邊的組合邏輯退化成一條“總頻次是不是1”代碼量大幅下降思維負(fù)擔(dān)也小很多。這也是我推薦合并計(jì)數(shù)的根本原因把數(shù)據(jù)先歸攏成一層再做判斷永遠(yuǎn)是處理這類問題的最穩(wěn)路徑。2.3 一次計(jì)數(shù)如何同時(shí)滿足“兩個(gè)條件”合并計(jì)數(shù)看起來像是繞過條件實(shí)際它是把所有條件的約束都折疊進(jìn)了“總數(shù)”這一個(gè)數(shù)字里。拆開理解就是如果總頻次是1那它把題目里的所有情況都包含了如果總頻次不是1那它一定在某個(gè)環(huán)節(jié)上違反了約束不管這個(gè)環(huán)節(jié)是“同句重復(fù)”還是“跨句都出現(xiàn)”。舉個(gè)具體例子s1 a a bs2 c。合并后得到a:2, b:1, c:1。輸出b和c。此時(shí)a雖然只在一個(gè)句子中出現(xiàn)但它自己句子內(nèi)部出現(xiàn)了兩次所以被踢掉b只出現(xiàn)一次c也只出現(xiàn)一次它們都符合。這個(gè)例子很好地說明了“出現(xiàn)一次”這個(gè)條件同時(shí)作用于句內(nèi)和句間而合并計(jì)數(shù)能一把梭全管住因?yàn)樗慌袛嘧罱K頻數(shù)。3. 哈希表詞頻統(tǒng)計(jì)三種語言的主路徑實(shí)現(xiàn)3.1 Python 最短實(shí)現(xiàn)與可讀性取舍Python 寫這道題有天然優(yōu)勢(shì)collections.Counter一行就能完成計(jì)數(shù)。from collections import Counter from typing import List class Solution: def uncommonFromSentences(self, s1: str, s2: str) - List[str]: words s1.split() s2.split() return [word for word, cnt in Counter(words).items() if cnt 1]這里s1.split()和s2.split()得到兩個(gè)單詞列表相加后得到一個(gè)完整的單詞列表Counter統(tǒng)計(jì)頻次列表推導(dǎo)式過濾出計(jì)數(shù)為1的單詞。整個(gè)過程沒有多余的手工循環(huán)。有一個(gè)可讀性上的取舍有人會(huì)在return前先counter Counter(words)然后res []循環(huán)添加這樣代碼更長(zhǎng)但初學(xué)者更容易讀懂。我不覺得一定要追求最短關(guān)鍵是合入列表后的Counter行為要清楚。另外Python 3.7 之后普通dict保持插入順序而Counter是dict的子類所以這里的輸出順序其實(shí)就是各單詞在合并后第一次出現(xiàn)的順序。如果面試官問“能不能保持首次出現(xiàn)順序”Python 這個(gè)寫法天然滿足。3.2 Java 實(shí)現(xiàn)Map.merge 的細(xì)節(jié)Java 沒有 Python 現(xiàn)成的計(jì)數(shù)器需要主動(dòng)處理Map的累加邏輯。我用的是getOrDefault方案class Solution { public String[] uncommonFromSentences(String s1, String s2) { MapString, Integer cnt new HashMap(); countWord(cnt, s1); countWord(cnt, s2); ListString res new ArrayList(); for (Map.EntryString, Integer entry : cnt.entrySet()) { if (entry.getValue() 1) { res.add(entry.getKey()); } } return res.toArray(new String[0]); } private void countWord(MapString, Integer cnt, String s) { for (String word : s.split(\\s)) { cnt.put(word, cnt.getOrDefault(word, 0) 1); } } }注意這里我用了s.split(\\s)而不是s.split( )。原題雖然說明句子由小寫字母和空格組成看起來一個(gè)空格分隔一個(gè)單詞但在真實(shí)輸入里連續(xù)多個(gè)空格很常見split( )在連續(xù)空格時(shí)會(huì)產(chǎn)生空字符串進(jìn)而把空串也當(dāng)成單詞計(jì)數(shù)。\\s能消除這種隱患而且不會(huì)影響單空格情況下的正確性。這是一個(gè)很小的習(xí)慣但能幫你少踩很多后端的坑。如果想展示更地道的 Java 寫法可以把put換成mergecnt.merge(word, 1, Integer::sum);這個(gè)寫法等價(jià)于“如果word不存在就放1存在就執(zhí)行Integer::sum累加”代碼更簡(jiǎn)潔但前提是面試時(shí)能解釋清楚merge的行為否則寫出來容易讓面試官覺得是在背API。兩種寫法都能過我平時(shí)習(xí)慣用getOrDefault因?yàn)樗鼘?duì)初學(xué)者更友好。3.3 C 實(shí)現(xiàn)與字符串切分的一個(gè)小坑C 語言沒有內(nèi)置split處理空格分隔的句子最自然的方式是用istringstream它天生按空白符切分多個(gè)空格、換行都能自動(dòng)略過。class Solution { public: vectorstring uncommonFromSentences(string s1, string s2) { unordered_mapstring, int cnt; auto countWord [](const string s) { istringstream iss(s); string word; while (iss word) { cnt[word]; } }; countWord(s1); countWord(s2); vectorstring ans; for (auto [word, c] : cnt) { if (c 1) { ans.push_back(word); } } return ans; } };這里cnt[word]是 C 哈希表計(jì)數(shù)的一個(gè)經(jīng)典寫法operator[]在鍵不存在時(shí)會(huì)自動(dòng)插入一個(gè)默認(rèn)值0然后自增于是第一次遇到某個(gè)單詞時(shí)它就變成1。不過要注意如果使用map而不是unordered_map輸出的順序會(huì)按照字典序排列但題目要求“可以按任意順序返回結(jié)果”所以兩者都行。從性能上unordered_map平均是O(1)插入查找map是O(log n)大部分時(shí)候選unordered_map更合適。如果不用istringstream而手寫循環(huán)按空格切分一個(gè)小問題是單詞末尾如果沒有空格很容易漏掉最后一個(gè)單詞有連續(xù)空格時(shí)又容易把空串推進(jìn)結(jié)果。istringstream把這些邊界全部兜住這才是它在這道題里最值得用的原因。三種語言的實(shí)現(xiàn)放到一起核心邏輯完全一樣差異只在“字符串切分方式”?？梢园阉鼈兛醋魍凰悸返娜N皮膚理解了合并計(jì)數(shù)后語言只是工具層面的區(qū)別。語言切分方式計(jì)數(shù)結(jié)構(gòu)最終過濾方式Pythonstr.split()Counter列表推導(dǎo)式Javasplit(\\s)HashMapgetOrDefault遍歷entrySetCistringstreamunordered_mapoperator[]遍歷迭代或結(jié)構(gòu)化綁定4. 邊界測(cè)試與復(fù)雜度把解法從“能跑”調(diào)到“無懈可擊”4.1 一組值得反復(fù)跑的測(cè)試用例寫完代碼后真正決定能不能一次通過的是邊界用例。LeetCode 這類題目的隱藏用例很喜歡卡“空字符串”“同詞重復(fù)”“兩邊對(duì)稱”這幾種情況。下面這組用例是我在本地必跑的輸入s1輸入s2期望輸出為什么[]雙空串沒有任何單詞a[a]一邊空另一邊單次出現(xiàn)a[a]對(duì)稱情況aa[]兩邊都出現(xiàn)總頻次為2a a[]同句重復(fù)即使另一邊為空也不算a a bc[b, c]a同句重復(fù)被過濾a ba[b]a兩邊都有總頻次2重點(diǎn)觀察a a和這個(gè)用例。很多人寫代碼時(shí)嘴上說著“統(tǒng)計(jì)所有單詞出現(xiàn)次數(shù)”但潛意識(shí)里總想把空串直接忽略。確實(shí)split()在 Java 中會(huì)返回一個(gè)長(zhǎng)度為1的數(shù)組元素是空串如果切分方式不嚴(yán)謹(jǐn)空串會(huì)被計(jì)入導(dǎo)致空句子被誤認(rèn)為包含一個(gè)單詞。Python 的.split()返回空列表不會(huì)有這個(gè)問題Java 的split(\\s)對(duì)空字符串同樣返回包含一個(gè)空串的數(shù)組。所以countWord里最好加一個(gè)if (word.isEmpty()) continue;的防御或者干脆用s.trim().split(\\s)并在循環(huán)里跳過空串。這種防御性判斷在本地可能用不上但面對(duì)真實(shí)項(xiàng)目的數(shù)據(jù)清洗時(shí)很值得保留。4.2 時(shí)間復(fù)雜度與空間復(fù)雜度的完整推導(dǎo)設(shè)s1拆出的單詞數(shù)為n1s2拆出的單詞數(shù)為n2總規(guī)模n n1 n2。時(shí)間上切分字符串需要掃描一遍句子統(tǒng)計(jì)時(shí)需要把每個(gè)單詞插入哈希表一次過濾時(shí)遍歷哈希表一次。哈希表單次操作平均O(1)所以總時(shí)間復(fù)雜度是O(n)?？臻g上哈希表最多存n個(gè)不同的鍵切分過程中產(chǎn)生的單詞列表在某些語言里也會(huì)額外占用空間總體空間復(fù)雜度也是O(n)。如果糾結(jié)常數(shù)Python 的s1.split() s2.split()會(huì)一次性創(chuàng)建兩個(gè)列表和一個(gè)新列表峰值內(nèi)存比逐個(gè)單詞處理要高一點(diǎn)。在 LeetCode 的輸入規(guī)模下完全無所謂但在討論系統(tǒng)設(shè)計(jì)時(shí)如果句子是幾GB級(jí)別的日志流這個(gè)寫法就不夠優(yōu)雅了需要改成“一邊讀一邊計(jì)數(shù)”的流式處理。不過對(duì)這道題O(n) 的時(shí)間和空間都是理論最優(yōu)不存在明顯的優(yōu)化量級(jí)空間面試官問性能時(shí)能脫口而出這個(gè)結(jié)論就行。4.3 為什么必須先全量統(tǒng)計(jì)不能邊遍歷邊判斷有沒有可能“在第一次遇到某個(gè)單詞時(shí)就立刻決定它是否進(jìn)結(jié)果”答案是不行。一個(gè)單詞最終是否輸出取決于它的總頻次是否等于1。如果它在前面出現(xiàn)了第一次我無法知道后面還會(huì)不會(huì)再出現(xiàn)一次如果我在第一次出現(xiàn)時(shí)就把它的頻率記在心里假設(shè)后邊又來一次前面的“預(yù)判決”就得撤回。所以無論如何都要先把整份數(shù)據(jù)過一遍得到完整頻次表再在第二輪遍歷時(shí)做過濾。這也是很多初寫者覺得“這個(gè)題那么簡(jiǎn)單我卻寫不順”的心理來源他們?cè)噲D在一次循環(huán)里既完成“發(fā)現(xiàn)新詞”又完成“判斷該不該輸出”但實(shí)際上這兩件事之間隔著一次完整掃描。解題時(shí)把這個(gè)道理想清楚代碼就會(huì)自然而然地變成“先統(tǒng)計(jì)、后收集”的兩段式結(jié)構(gòu)。4.4 常見易錯(cuò)點(diǎn)清單照我自己的刷題經(jīng)驗(yàn)這道題的失分點(diǎn)集中在下面幾個(gè)地方用Set去重并做差集丟失頻數(shù)信息導(dǎo)致同句重復(fù)單詞被錯(cuò)誤輸出。用兩個(gè)Map分別統(tǒng)計(jì)時(shí)判斷條件只覆蓋了“左有右無”和“右有左無”漏掉了“同句出現(xiàn)兩次”的過濾。Java 使用split( )遇到連續(xù)空格或空字符串時(shí)把空串計(jì)入哈希表。使用HashMap后期望結(jié)果保持某種固定順序其實(shí)題目明確說順序任意這是多慮了。輸出數(shù)組類型不匹配Java 里忘了把ListString轉(zhuǎn)成String[]。這些坑都不是算法層面的而是“偽直覺”和“語言細(xì)節(jié)”混在一起造成的。先把等價(jià)條件想齊再寫代碼前面四項(xiàng)基本自動(dòng)消失。5. 換個(gè)問法與真實(shí)場(chǎng)景這個(gè)題的擴(kuò)展價(jià)值和實(shí)際映射5.1 如果題目要求“按原順序返回”怎么寫LeetCode 原題不要求順序但面試官可能會(huì)加一句“能不能讓結(jié)果按照單詞在兩個(gè)句子中首次出現(xiàn)的順序排列”此時(shí)需要注意不同語言的表現(xiàn)。Python 版本天然滿足因?yàn)镃ounter保持首次遇到鍵的順序items()的迭代順序也是插入順序。Java 版本需要把HashMap換成LinkedHashMap因?yàn)镠ashMap不保證順序LinkedHashMap才按插入順序迭代。C 版本麻煩一點(diǎn)unordered_map不保證任何穩(wěn)定順序要額外在統(tǒng)計(jì)時(shí)記錄每個(gè)單詞第一次出現(xiàn)的下標(biāo)最后排序輸出。如果只按首次出現(xiàn)順序而不需要按字典序我一般用一個(gè)ListString按遇到順序存鍵再結(jié)合Map判斷該不該輸出。這個(gè)變體的本質(zhì)是“保持順序需要額外記錄順序信息”而它并不改變數(shù)據(jù)結(jié)構(gòu)和算法的主干仍然是一次統(tǒng)計(jì)、一次過濾。5.2 從兩句話推廣到 N 句話把“兩個(gè)句子”改成“N 個(gè)段落”條件變成“找出在所有文本中總共只出現(xiàn)一次的單詞”解題思路不需要大改仍然是合并所有段落、統(tǒng)一統(tǒng)計(jì)詞頻、收集頻次為1的單詞。此時(shí)合并計(jì)數(shù)的優(yōu)勢(shì)更明顯你不需要為每個(gè)段落分別維護(hù)一個(gè)表只需要一個(gè)全局限量表。如果用最笨的辦法為N個(gè)段落分配N個(gè)Map再兩兩比較復(fù)雜度會(huì)急劇膨脹。合并成一個(gè)表之后數(shù)據(jù)規(guī)模從“句子個(gè)數(shù) × 句子內(nèi)單詞數(shù)”變成了“總單詞數(shù)”處理邏輯反而與句子個(gè)數(shù)解耦。這個(gè)推廣對(duì)真實(shí)項(xiàng)目有直接意義日志分析中經(jīng)常要跨多個(gè)日志文件找出只出現(xiàn)過一次的會(huì)話ID思路和本題一模一樣。5.3 “詞頻為1”在文本場(chǎng)景中的真實(shí)含義從文本處理的角度想“出現(xiàn)次數(shù)為1”往往是一個(gè)稀有度信號(hào)。比如在一批客服對(duì)話中某個(gè)商品型號(hào)只有一次提及可能是因?yàn)檫@個(gè)型號(hào)太新、太冷門也可能是用戶輸入錯(cuò)誤。這類低頻詞在NLP預(yù)處理中經(jīng)常會(huì)被過濾掉防止它們?cè)谀Ｐ陀?xùn)練時(shí)造成過擬合。這道題取的是cnt 1而工業(yè)界的通用做法可能是cnt 3或cnt 5邏輯上是一脈相承的先做精確頻次統(tǒng)計(jì)再按頻次閾值篩選關(guān)鍵項(xiàng)目。另一個(gè)真實(shí)場(chǎng)景是文檔對(duì)比工具。兩份合同或配置文件的差異往往體現(xiàn)在“只在一個(gè)文件中出現(xiàn)一次的術(shù)語”上。把這兩份文檔當(dāng)成s1和s2這套算法能直接提取出只屬于某一方的特殊名詞用來輔助人工核查。本質(zhì)上它就是在做“精確文本指紋”的分析。5.4 我個(gè)人的一點(diǎn)實(shí)操體會(huì)這道題讓我印象最深的不是解法本身而是“從題面到等價(jià)條件”的那一步。很多刷題攻略會(huì)告訴你“看到統(tǒng)計(jì)次數(shù)用哈希表”但真正容易錯(cuò)的是把“不常見”理解成“不對(duì)稱”。我在實(shí)際寫代碼前把題目條件拆成了“恰好一次 只在一邊”又驗(yàn)證了“兩邊合計(jì)一次”是否等價(jià)最后才動(dòng)手實(shí)現(xiàn)。這個(gè)驗(yàn)證過程花了兩分鐘卻幫我避免了一整輪的返工。所以我的建議是遇到這類文字條件較多的題目先別急著打開編輯器拿紙筆把條件的等價(jià)表述寫出來往往比直接寫代碼更快得到正確答案。這里的道理也適用到其他哈希表題目先搞清楚你要數(shù)的是什么再?zèng)Q定用什么容器去數(shù)。最后如果你現(xiàn)在正刷到這道題不妨順手在本地跑一遍第4節(jié)那張用例表特別關(guān)注a a和空串的組合。把這些邊界跑通了你對(duì)“詞頻統(tǒng)計(jì)”這類題的理解會(huì)比單純提交通過更扎實(shí)。