LeetCode 884题名很长Uncommon Words from Two Sentences中文一般翻译成两句话中的不常见单词。第一次刷这题的人多半会觉得它简单给两个句子把出现次数少的单词找出来嘛。可我在实际提交前一度想用“集合差集”去解结果写完才发现逻辑上有个洞最后老老实实回到哈希表词频统计。这道题虽然只是哈希计数的基础应用但它恰好卡在一个很经典的直觉误区上“只在一边出现过”并不等于“两边都不常见”。这篇内容适合三类读者刚学完哈希表想找入门题巩固的面试前快速过一遍字符串处理套路的以及想搞清楚“为什么这类题不能靠往下拆两三个判断条件硬写”的人。题目本身没有任何高端算法时间空间复杂度都是O(n)但它对“条件等价转化”的要求非常典型值得拆开揉碎讲一遍。我会从题面理解、反直觉反例、三种语言实现、边界与复杂度、再到业务场景的映射完整过一遍我自己的解题思路和踩坑心得。1. 题面读完先别急着写代码这道题到底在问什么1.1 原题输入输出速览题目给两个字符串句子s1和s2句子里的单词都由小写字母组成单词之间用空格分隔。要求返回一个字符串数组数组里装的是所有“不常见单词”。什么算不常见原题的定义是这个单词在恰好一个句子里出现且在这个句子里恰好出现一次。举个例子s1 this apple is sweets2 this apple is sour输出是[sweet, sour]。因为this、apple、is两个句子都出现了不是不常见而sweet只在第一句出现一次sour只在第二句出现一次这两个才能进结果。再看另一个例子s1 apple apples2 banana。按直觉apple在第一句里出现了两次所以它不算“恰好出现一次”不能输出banana只出现一次可以输出。结果为[banana]。这个例子很关键它直接把很多人的第一反应打掉了仅仅保证“另一个句子没有”是不够的你自己的句子内部也不能有重复。1.2 “只出现一次”到底限定在哪个集合我刚刷到这题时脑子里冒出来的第一句话是“找出只在一边出的词。”这个说法很模糊因为“只在一边”可以有至少两种解读解读A这个单词出现在s1中且不出现在s2中或出现在s2中且不出现在s1中。至于它在自己所在的句子里出现几次不管。解读B这个单词在两个句子中合计只出现一次。题目要的是解读B。apple apple的例子能说明问题apple确实只在s1中出现、s2中没有但它出现了两次按解读A也过不了“恰好出现一次”按解读B同样过不了。两个解读在这个例子上恰好结论一致真正区分它们的是更极端的场景s1 a bs2 a a b b。按解读Aa和b都在两个句子中出现了谁都不是“只在一边”结果应该为空按解读Ba和b的总出现次数都大于1结果同样为空。看起来还是一致。这两者真正产生分歧的场景是一个单词在自己句子中出现了两次但另一边完全没有。比如s1 x xs2 y。解读A会说x只在左边出现算不常见解读B会说x总共出现两次不算。题目要的是解读B。所以千万不能把逻辑简化成“看单词属于哪边的集合”而必须把“出现频次”焊死在判断条件里。1.3 一句等价的话让解法直接定型把解读B再翻译一下一个单词在两个句子中合计出现次数恰好等于1。这个等价转化是整个题的精髓。为什么它等价从定义出发一个不常见单词必须满足两个条件在某个句子中恰好出现一次在另一个句子中完全没出现。这本质上说明它横跨两个句子的总次数就是1。反过来看如果某个单词的总出现次数正好是1那么它不可能同时出现在两个句子中也不可能在同一个句子中出现两次它的唯一一次出现一定落在某一个句子里。因此“总频次 1”和题目定义完全互相推出。一旦把这个等价关系写出来解法就非常老套了把两个句子的所有单词合并成一个单词流统计每个单词的出现次数最后挑出计数等于1的那些单词返回。整个过程和句子数量无关只和单词流有关。这个转化虽然简单但我觉得它才是本题真正的考点很多写法绕来绕去写一大堆if条件其实就是没意识到这个等价关系。2. 为什么不能直接取两句话的单词差集2.1 集合操作丢掉频数必翻车不少人的第一反应是用集合把s1拆成一个Set把s2拆成一个Set然后对两个集合做“对称差集”——也就是(set1 - set2) (set2 - set1)把只在一边出现的单词收集起来。这套思路对“两个句子各有一个相同单词但这个单词出现了两次”的情况会直接失效。比如s1 b bs2 c c。两个集合都是去重的结果set1 {b}set2 {c}对称差集是{b, c}于是错误地返回两个单词。但按题目标准b在第一句出现了两次c在第二句出现了两次它们都不满足“恰好出现一次”正确答案应该是空数组。问题出在Set把“出现次数”这个信息揉碎了。集合只能回答“这个单词存不存在”回答不了“它出现了几遍”。而本题要求的“恰好出现一次”恰恰是频数信息不是存在性信息。所以凡是用Set或“去重后取差集”的方案在出现同句重复词的时候都会或多或少的出问题。2.2 两个 Map 分别计数可行但比合并计数更绕那有人会说“我不去重用两个Map分别统计每个句子的词频然后遍历的时候判断freq1.get(w)1 !freq2.containsKey(w)反过来再处理一遍行不行”答案是可行的但非常容易出错。假设w在s1中出现一次在s2中也出现一次此时freq1.get(w)1且freq2.containsKey(w)true按上面的条件不会输出没毛病。但如果我写的判断条件是“freq1.get(w)1且freq2.getOrDefault(w,0)0”那是对的。问题就在于一旦条件写复杂就很容易漏掉某条分支比如w在两个句子中各自出现一次的情况有些人的直觉是“两边都出现肯定不常见”于是没写判断结果倒是误打误撞对了。真正麻烦的是w在s1中出现两次且s2中没出现此时freq1.get(w)2第一个条件就不满足正确跳过。这样分两个Map写每个单词要查两次表还要考虑左右两边的对称性代码容易变得臃肿也更容易在边界上失误。合并成一个Map之后判断条件从两条边的组合逻辑退化成一条“总频次是不是1”代码量大幅下降思维负担也小很多。这也是我推荐合并计数的根本原因把数据先归拢成一层再做判断永远是处理这类问题的最稳路径。2.3 一次计数如何同时满足“两个条件”合并计数看起来像是绕过条件实际它是把所有条件的约束都折叠进了“总数”这一个数字里。拆开理解就是如果总频次是1那它把题目里的所有情况都包含了如果总频次不是1那它一定在某个环节上违反了约束不管这个环节是“同句重复”还是“跨句都出现”。举个具体例子s1 a a bs2 c。合并后得到a:2, b:1, c:1。输出b和c。此时a虽然只在一个句子中出现但它自己句子内部出现了两次所以被踢掉b只出现一次c也只出现一次它们都符合。这个例子很好地说明了“出现一次”这个条件同时作用于句内和句间而合并计数能一把梭全管住因为它只判断最终频数。3. 哈希表词频统计三种语言的主路径实现3.1 Python 最短实现与可读性取舍Python 写这道题有天然优势collections.Counter一行就能完成计数。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()得到两个单词列表相加后得到一个完整的单词列表Counter统计频次列表推导式过滤出计数为1的单词。整个过程没有多余的手工循环。有一个可读性上的取舍有人会在return前先counter Counter(words)然后res []循环添加这样代码更长但初学者更容易读懂。我不觉得一定要追求最短关键是合入列表后的Counter行为要清楚。另外Python 3.7 之后普通dict保持插入顺序而Counter是dict的子类所以这里的输出顺序其实就是各单词在合并后第一次出现的顺序。如果面试官问“能不能保持首次出现顺序”Python 这个写法天然满足。3.2 Java 实现Map.merge 的细节Java 没有 Python 现成的计数器需要主动处理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( )。原题虽然说明句子由小写字母和空格组成看起来一个空格分隔一个单词但在真实输入里连续多个空格很常见split( )在连续空格时会产生空字符串进而把空串也当成单词计数。\\s能消除这种隐患而且不会影响单空格情况下的正确性。这是一个很小的习惯但能帮你少踩很多后端的坑。如果想展示更地道的 Java 写法可以把put换成mergecnt.merge(word, 1, Integer::sum);这个写法等价于“如果word不存在就放1存在就执行Integer::sum累加”代码更简洁但前提是面试时能解释清楚merge的行为否则写出来容易让面试官觉得是在背API。两种写法都能过我平时习惯用getOrDefault因为它对初学者更友好。3.3 C 实现与字符串切分的一个小坑C 语言没有内置split处理空格分隔的句子最自然的方式是用istringstream它天生按空白符切分多个空格、换行都能自动略过。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 哈希表计数的一个经典写法operator[]在键不存在时会自动插入一个默认值0然后自增于是第一次遇到某个单词时它就变成1。不过要注意如果使用map而不是unordered_map输出的顺序会按照字典序排列但题目要求“可以按任意顺序返回结果”所以两者都行。从性能上unordered_map平均是O(1)插入查找map是O(log n)大部分时候选unordered_map更合适。如果不用istringstream而手写循环按空格切分一个小问题是单词末尾如果没有空格很容易漏掉最后一个单词有连续空格时又容易把空串推进结果。istringstream把这些边界全部兜住这才是它在这道题里最值得用的原因。三种语言的实现放到一起核心逻辑完全一样差异只在“字符串切分方式”。可以把它们看作同一思路的三种皮肤理解了合并计数后语言只是工具层面的区别。语言切分方式计数结构最终过滤方式Pythonstr.split()Counter列表推导式Javasplit(\\s)HashMapgetOrDefault遍历entrySetCistringstreamunordered_mapoperator[]遍历迭代或结构化绑定4. 边界测试与复杂度把解法从“能跑”调到“无懈可击”4.1 一组值得反复跑的测试用例写完代码后真正决定能不能一次通过的是边界用例。LeetCode 这类题目的隐藏用例很喜欢卡“空字符串”“同词重复”“两边对称”这几种情况。下面这组用例是我在本地必跑的输入s1输入s2期望输出为什么[]双空串没有任何单词a[a]一边空另一边单次出现a[a]对称情况aa[]两边都出现总频次为2a a[]同句重复即使另一边为空也不算a a bc[b, c]a同句重复被过滤a ba[b]a两边都有总频次2重点观察a a和这个用例。很多人写代码时嘴上说着“统计所有单词出现次数”但潜意识里总想把空串直接忽略。确实split()在 Java 中会返回一个长度为1的数组元素是空串如果切分方式不严谨空串会被计入导致空句子被误认为包含一个单词。Python 的.split()返回空列表不会有这个问题Java 的split(\\s)对空字符串同样返回包含一个空串的数组。所以countWord里最好加一个if (word.isEmpty()) continue;的防御或者干脆用s.trim().split(\\s)并在循环里跳过空串。这种防御性判断在本地可能用不上但面对真实项目的数据清洗时很值得保留。4.2 时间复杂度与空间复杂度的完整推导设s1拆出的单词数为n1s2拆出的单词数为n2总规模n n1 n2。时间上切分字符串需要扫描一遍句子统计时需要把每个单词插入哈希表一次过滤时遍历哈希表一次。哈希表单次操作平均O(1)所以总时间复杂度是O(n)。空间上哈希表最多存n个不同的键切分过程中产生的单词列表在某些语言里也会额外占用空间总体空间复杂度也是O(n)。如果纠结常数Python 的s1.split() s2.split()会一次性创建两个列表和一个新列表峰值内存比逐个单词处理要高一点。在 LeetCode 的输入规模下完全无所谓但在讨论系统设计时如果句子是几GB级别的日志流这个写法就不够优雅了需要改成“一边读一边计数”的流式处理。不过对这道题O(n) 的时间和空间都是理论最优不存在明显的优化量级空间面试官问性能时能脱口而出这个结论就行。4.3 为什么必须先全量统计不能边遍历边判断有没有可能“在第一次遇到某个单词时就立刻决定它是否进结果”答案是不行。一个单词最终是否输出取决于它的总频次是否等于1。如果它在前面出现了第一次我无法知道后面还会不会再出现一次如果我在第一次出现时就把它的频率记在心里假设后边又来一次前面的“预判决”就得撤回。所以无论如何都要先把整份数据过一遍得到完整频次表再在第二轮遍历时做过滤。这也是很多初写者觉得“这个题那么简单我却写不顺”的心理来源他们试图在一次循环里既完成“发现新词”又完成“判断该不该输出”但实际上这两件事之间隔着一次完整扫描。解题时把这个道理想清楚代码就会自然而然地变成“先统计、后收集”的两段式结构。4.4 常见易错点清单照我自己的刷题经验这道题的失分点集中在下面几个地方用Set去重并做差集丢失频数信息导致同句重复单词被错误输出。用两个Map分别统计时判断条件只覆盖了“左有右无”和“右有左无”漏掉了“同句出现两次”的过滤。Java 使用split( )遇到连续空格或空字符串时把空串计入哈希表。使用HashMap后期望结果保持某种固定顺序其实题目明确说顺序任意这是多虑了。输出数组类型不匹配Java 里忘了把ListString转成String[]。这些坑都不是算法层面的而是“伪直觉”和“语言细节”混在一起造成的。先把等价条件想齐再写代码前面四项基本自动消失。5. 换个问法与真实场景这个题的扩展价值和实际映射5.1 如果题目要求“按原顺序返回”怎么写LeetCode 原题不要求顺序但面试官可能会加一句“能不能让结果按照单词在两个句子中首次出现的顺序排列”此时需要注意不同语言的表现。Python 版本天然满足因为Counter保持首次遇到键的顺序items()的迭代顺序也是插入顺序。Java 版本需要把HashMap换成LinkedHashMap因为HashMap不保证顺序LinkedHashMap才按插入顺序迭代。C 版本麻烦一点unordered_map不保证任何稳定顺序要额外在统计时记录每个单词第一次出现的下标最后排序输出。如果只按首次出现顺序而不需要按字典序我一般用一个ListString按遇到顺序存键再结合Map判断该不该输出。这个变体的本质是“保持顺序需要额外记录顺序信息”而它并不改变数据结构和算法的主干仍然是一次统计、一次过滤。5.2 从两句话推广到 N 句话把“两个句子”改成“N 个段落”条件变成“找出在所有文本中总共只出现一次的单词”解题思路不需要大改仍然是合并所有段落、统一统计词频、收集频次为1的单词。此时合并计数的优势更明显你不需要为每个段落分别维护一个表只需要一个全局限量表。如果用最笨的办法为N个段落分配N个Map再两两比较复杂度会急剧膨胀。合并成一个表之后数据规模从“句子个数 × 句子内单词数”变成了“总单词数”处理逻辑反而与句子个数解耦。这个推广对真实项目有直接意义日志分析中经常要跨多个日志文件找出只出现过一次的会话ID思路和本题一模一样。5.3 “词频为1”在文本场景中的真实含义从文本处理的角度想“出现次数为1”往往是一个稀有度信号。比如在一批客服对话中某个商品型号只有一次提及可能是因为这个型号太新、太冷门也可能是用户输入错误。这类低频词在NLP预处理中经常会被过滤掉防止它们在模型训练时造成过拟合。这道题取的是cnt 1而工业界的通用做法可能是cnt 3或cnt 5逻辑上是一脉相承的先做精确频次统计再按频次阈值筛选关键项目。另一个真实场景是文档对比工具。两份合同或配置文件的差异往往体现在“只在一个文件中出现一次的术语”上。把这两份文档当成s1和s2这套算法能直接提取出只属于某一方的特殊名词用来辅助人工核查。本质上它就是在做“精确文本指纹”的分析。5.4 我个人的一点实操体会这道题让我印象最深的不是解法本身而是“从题面到等价条件”的那一步。很多刷题攻略会告诉你“看到统计次数用哈希表”但真正容易错的是把“不常见”理解成“不对称”。我在实际写代码前把题目条件拆成了“恰好一次 只在一边”又验证了“两边合计一次”是否等价最后才动手实现。这个验证过程花了两分钟却帮我避免了一整轮的返工。所以我的建议是遇到这类文字条件较多的题目先别急着打开编辑器拿纸笔把条件的等价表述写出来往往比直接写代码更快得到正确答案。这里的道理也适用到其他哈希表题目先搞清楚你要数的是什么再决定用什么容器去数。最后如果你现在正刷到这道题不妨顺手在本地跑一遍第4节那张用例表特别关注a a和空串的组合。把这些边界跑通了你对“词频统计”这类题的理解会比单纯提交通过更扎实。