哈希表词频统计实战：力扣884两句话中的不常见单词

力扣第884题《Uncommon Words from Two Sentences》中文名叫“两句话中的不常见单词”是一道看起来简单、实际藏着不少考点的字符串哈希题。它同时训练你三件事把自然语言描述翻译成等价算法、熟练使用哈希表做词频统计、严谨处理边界条件。所以它经常出现在新手刷题路线图的前几十题里也偶尔作为面试热身题出现——毕竟字符串处理和词频统计是面试高频考点。如果你刚学完哈希表想找一道题练手这题非常合适如果你在准备面试想快速复习“词频统计类”题目的通用模板这题同样值得花十分钟过一遍。题目要求很直接给两个句子s1和s2返回所有不常见单词。句子里的单词由空格分隔只含小写字母。我第一次做这道题时差点被“不常见单词”这个说法带偏。直觉上应该把两个句子分开处理先看s1里哪些词只出现一次再看s2里哪些词只出现一次然后排除在另一个句子里出现过的。这么想逻辑没错但实现起来又长又绕。后来我找到了一条捷径把两个句子拼成一个长串统计所有单词的总频次频次等于1的就是答案。为什么可以这样下面一步步拆开讲。1. 先读懂题意不常见单词究竟指什么1.1 把题目定义翻译成等价条件题目原文对“不常见单词”的定义是一个单词在其中一个句子中恰好出现一次且不出现在另一个句子中。翻译成人话就是两个条件缺一不可条件一单词在s1或s2中的某一个句子里恰好出现一次。条件二这个单词在另一个句子里一次都没有出现。关键来了把两个句子合并成一个长文本后这两个条件会压缩成一条——单词在合并后的文本里总出现次数等于1。为什么因为如果某个单词在合并文本里总共只出现1次那它在两个句子里的总贡献就是1只可能是某个句子贡献了这1次另一个句子贡献了0。这不恰好满足“在某一句恰好一次、在另一句没出现”吗反过来推也一样任何满足原定义的词在合并文本里一定只出现一次。用一个例子验证一下。s1 this apple is sweet s2 this apple is sour合并后的单词列表为[this, apple, is, sweet, this, apple, is, sour]统计频率this2apple2is2sweet1sour1。所以答案是[sweet, sour]。再看一个边界一点的例子。s1 apple apple s2 banana合并后频率apple2banana1。答案是[banana]。apple虽然只出现在一个句子中但它出现了两次不满足“恰好一次”所以不能进入结果。这个例子很好地提醒我们不要把“不常见”错误理解成“只要没在另一句出现过就算”。1.2 常见的错误理解为什么有人会绕路我见过不少初学者把“不常见”理解成“在两个句子中出现次数都比较少”然后分别统计两边的低频词。这种思路在部分用例下碰巧能对但逻辑是错的。举一个反例同一个词在s1和s2里各出现一次。分开统计时这个词在每个句子里的频率都是1看起来“很稀有”但它其实不是不常见单词因为它同时出现在两个句子里违反了“不出现在另一个句子中”这条硬性条件。还有一种误区是“只在一个句子出现就算”不要求恰好一次。比如s1 dog dog cats2 apple合并后dog出现2次不是不常见但按“只在一句出现”的逻辑会把dog也算进去。为什么大家都爱绕路因为题目定义给了两个并列条件中文翻译“不常见”又是个模糊的形容词很容易让人往复杂方向想。面这道题时面试官往往就是看你能不能把这个定义做一步等价变换用“全局只出现一次”这个更简洁的条件来表达。能说出来说明你抓住了本质。2. 核心解法用哈希表做词频统计2.1 为什么哈希表是这类问题的最优选词频统计这件事背后的核心数据结构就是哈希表。哈希表提供“单词到次数”的映射插入和查找都是平均O(1)。你可以把它想象成每个单词专属的计数卡读到一个单词就翻出它的卡片划一道杠全部处理完后哪张卡片上只有一道杠哪个单词就是答案。对比一下其他方案方案思路时间复杂度空间复杂度评价哈希表每个词对应一个计数器O(n)O(k)首选代码短且直观排序扫描排序后相同单词相邻数连续段长度O(n log n)O(1)或O(n)可行但代码更长双重循环暴力每个单词与所有单词逐一比较O(n^2)O(1)大数据量容易超时不推荐为什么不选数组因为单词不是连续整数没法直接当数组下标来用还得额外设计一套映射逻辑绕远路。为什么不优先排序排序能做但要多付出O(n log n)而且相邻比较的细节容易写错。哈希表既贴合“按key查value”的模型在时间复杂度上又占优所以它几乎是这类词频题的标准答案。2.2 Python实现一行流与逐步写法先看最简洁的一行流版本from collections import Counter def uncommon_from_sentences(s1: str, s2: str) - list[str]: words (s1 s2).split() return [w for w, cnt in Counter(words).items() if cnt 1]这行代码能成立依赖三个细节。第一s1 s2中间必须补一个空格否则s1的末尾单词会和s2的开头单词粘成一个新词。第二split()默认按所有空白字符切分会忽略首尾空白即使s1是空字符串得到的结果也是[]不会混入空字符串。第三Counter(words)直接对单词列表做频次统计遍历items()拿到“单词:次数”对再用列表推导式筛选出计数恰好为1的单词。不过我更推荐面试时用逐步写法from collections import Counter def uncommon_from_sentences(s1: str, s2: str) - list[str]: combined s1 s2 words combined.split() freq Counter(words) result [] for word, count in freq.items(): if count 1: result.append(word) return result逐步写法的每一步都可以当成一句解说词先合并再拆词再统计最后筛选。面试官能跟着你的思路走你也不用担心写太花哨的语法被追问。而且中途如果发现结果不对逐步写法更容易插入调试语句。2.3 Java 与 C 的参考实现并不是所有面试都会用PythonJava和C的写法更常见于后端岗位。Java版本class Solution { public String[] uncommonFromSentences(String s1, String s2) { MapString, Integer count new HashMap(); String[] words (s1 s2).split( ); for (String word : words) { count.put(word, count.getOrDefault(word, 0) 1); } ListString result new ArrayList(); for (Map.EntryString, Integer entry : count.entrySet()) { if (entry.getValue() 1) { result.add(entry.getKey()); } } return result.toArray(new String[0]); } }C版本#include string #include vector #include unordered_map #include sstream std::vectorstd::string uncommonFromSentences(std::string s1, std::string s2) { std::unordered_mapstd::string, int count; std::istringstream iss(s1 s2); std::string word; while (iss word) { count[word]; } std::vectorstd::string result; for (auto [word, cnt] : count) { if (cnt 1) result.push_back(word); } return result; }Java 这里要特别提醒一个坑.split( )返回的数组长度是1里面是一个空字符串。这个空串会进入HashMap最终结果里多出一个空串。稳妥做法是拆分前先trim()或者干脆用split(\\s)按多个空白字符切分。C 的istringstream word天然跳过连续空白和空串所以没有这个烦恼。2.4 不依赖 Counter 的手写统计如果面试官追问“不用内置的 Counter 怎么写”或者语言环境没有现成计数容器手写字典统计也很简单def uncommon_from_sentences(s1: str, s2: str) - list[str]: words (s1 s2).split() freq {} for w in words: freq[w] freq.get(w, 0) 1 return [w for w, c in freq.items() if c 1]核心就一行freq[w] freq.get(w, 0) 1。freq.get(w, 0)的意思是如果w不在字典里取默认值0如果已经存在取当前计数。加1再写回统计就完成了。这个写法比Counter更像“从零开始手写算法”能展示出自己的基本功建议每个刷题的人都默写一遍。3. 复杂度分析与边界案例3.1 时间复杂度和空间复杂度设两个句子一共有n个单词。split扫描一遍得到所有单词时间复杂度O(n)哈希表插入每个单词一次总体O(n)最后遍历哈希表筛选也是O(n)。所以总时间复杂度是O(n)。空间上哈希表里存的是不重复单词的计数假设有k个不同单词空间就是O(k)。最坏情况所有单词都不重复k约等于n最好情况所有单词都一样k等于1。这个复杂度已经是线性下界因为至少得看一遍所有字符所以一般面试里不需要再追求更低的复杂度。3.2 容易被忽略的边界条件速查刷这类题边界条件决定了代码的可靠性。我整理了一份自测用例表输入预期结果解释s1 ,s2 []没有单词自然没有不常见单词s1 a,s2 [a]a在一个句子里恰好一次另一个句子没有s1 a,s2 a[]合并后a频次为2s1 a a,s2 b[b]a出现两次不符合“恰好一次”s1 a b,s2 a c[b,c]a出现在两个句子频次为2另外要注意题目说了句子只包含小写字母和空格所以默认不需要处理大小写和标点。但如果面试官扩展场景比如要求大小写不敏感可以在拆词之后统一调lower()。3.3 自测用例与结果顺序问题自己验证代码时建议用sorted比较结果。因为哈希表的遍历顺序不固定[b,c]和[c,b]在数学上都正确但直接用列表相等判断会误报错误。def run_tests(): cases [ (this apple is sweet, this apple is sour, [sweet, sour]), (apple apple, banana, [banana]), (, , []), (a, , [a]), (a, a, []), ] for s1, s2, expected in cases: result uncommon_from_sentences(s1, s2) assert sorted(result) sorted(expected), (s1, s2, result, expected) print(all tests passed)线上刷题平台一般按集合校验结果顺序不影响通过。但本地调试这样写能避免因为顺序问题造成的误判。4. 实操中的常见坑与排查技巧4.1 拼接字符串时忘了加空格最经典的错误是(s1 s2).split()。比如s1 hellos2 world直接拼成helloworld两个单词的边界消失了。这是极端低级但发生率极高的错误我第一次提交就踩过。拼接的意义是让两个句子共用同一次词频统计中间必须有分隔符。4.2 split 的两种写法差别很大Python 的split()和split( )在本题里有本质区别。split()以任意连续空白为分隔符自动丢弃空串split( )严格以单个空格切分。对空字符串来说.split()返回[]而.split( )返回[]。如果用了后者且输入有空句子空串会进入Counter最后结果里就会出现一个空字符串导致提交失败。所以这道题我推荐一律用split()。虽然题目说句子是单个空格分隔但工程实践中数据永远比题目描述脏。用split()还能自动处理多个连续空格、tab 符和首尾空格让代码更健壮。4.3 把简单问题写成复杂分支有些人把问题拆成两个方向判断s1中恰好一次且不在s2的词再判断s2中恰好一次且不在s1的词。这么写确实能过但代码长度直接翻倍还多出大量in判断出错的概率也更高。合并统计最大的好处是不需要去思考“哪个句子”所有词一视同仁进入同一个计数器只看全局计数。这种“消除方向判断”的思路在很多题目里都能用比如找两个数组的交集、找出现奇数次的元素。遇到两个输入的东西先想想能不能合成一个数据集统一处理这往往是最优解。4.4 调试词频题的通用流程本地调试时打印两个中间变量基本就能定位 99% 的问题words (s1 s2).split() print(words) freq Counter(words) print(freq)如果words里多了空串去查split的用法。如果单词边界不对去查拼接那行。如果freq里某些词计数和预期不一致拿输入重新手工数一遍。提交前建议按四个用例自检题目示例、空字符串、两个句子完全相同、一个词出现三次。这四个用例能挡住绝大多数隐形错误。我每次刷词频类题目都会强制自己走一遍这个流程省了很多无意义的提交。5. 思路迁移一个模板解决一类词频问题5.1 这类题在面试里的出现方式力扣上有大量题目本质都是“统计频率 按条件筛选”。高频的有找数组中出现次数超过一半的元素。找两个数组的交集。判断两个字符串是否互为字母异位词。返回字符串中出现频率最高的前 k 个元素。它们的核心结构一模一样把数据拆成可哈希的元素放进计数器然后筛选满足条件的元素。第884题就是这套模板里最简单的一道吃透它等于给后面这些题打好了地基。5.2 一个可以复用的Python模板from collections import Counter def frequency_filter(elements, condition): freq Counter(elements) return [item for item, count in freq.items() if condition(count)]condition是一个谓词函数比如lambda c: c 1就是本题lambda c: c n // 2就是“多数元素”题。把筛选逻辑抽出来模板的扩展性就出来了。我刷题时会刻意把这类题归到同一个笔记下面试前扫一眼模板就能快速回忆起来。5.3 面试中的加分表达与常见追问面试遇到这题推荐按这样的顺序表达先说一句“本质上是合并两个句子统计全局词频计数等于1的词就是答案。”一句话点明题意。给出复杂度O(n) 时间O(k) 空间。主动补充边界情况空句子、重复词、两个句子都出现同一个词。写完代码后自己拿一个用例跑一遍验证。如果面试官进一步追问“如果单词太多内存放不下怎么办”思路可以转向分批统计加外部排序或者用哈希分桶把单词映射到多个小文件分别统计后再汇总。这就能把话题从简单题自然引向大数据处理是一个很自然的加分点。根据我的个人经验这种看似简单的小题在面试中的作用是“展示思维习惯”。同样一道题有人上来就写双重循环有人会先问单词是否区分大小写、句子是否一定非空后者往往更受面试官认可。养成先澄清边界、再动手写码的习惯能让你在大多数算法面试里都比别人稳。最后说一点我自己的体会。这道题我前后刷过三四遍第一遍写的是分开统计的复杂版本第二遍才悟到合并统计的写法。从那以后我只要遇到“从一段文本或数组里筛选满足频次条件元素”的题目都会先问自己一句能不能把输入合并成一条数据流只做一次全局统计大多数时候答案是能。这个思维切换帮我节省了大量编码时间也让我在面试讲题时更有条理。如果你也刚开始刷算法题建议把这道题作为练手第一梯队重点不是背代码而是体会那个“从两部分变成一部分”的转换过程。