哈希表实战：LeetCode 383赎金信解题思路与C++实现

刷题刷到哈希表这一章的时候很多人都会先做242. 有效的字母异位词紧接着就是383. 赎金信。这道题在代码随想录的题单里并不起眼甚至第一次看会觉得“这不就是count一下字符次数吗”但实际自己动手写的时候不少人会在“到底该用数组还是map”“为什么统计完还要减回去”这些地方卡一下。这篇文章就围绕哈希表这一核心主题把383. 赎金信的解题思路、C实现、边界条件和踩坑经验完整拆开讲一遍希望能帮你彻底吃透这道题顺便把“什么时候用数组当哈希表”这件事也搞清楚。1. 读懂题目赎金信到底在考什么1.1 题目背景与核心约束先明确一下题目本身。LeetCode 383. Ransom Note中文翻译成“赎金信”。背景故事挺有意思一个绑匪写了一封勒索信但他不想暴露笔迹所以打算从杂志里把字母一个一个剪下来拼成这封信。题目给了两个字符串ransomNote是你想拼出来的信magazine是手头那本杂志的内容要判断magazine里的字母能不能凑出ransomNote。放到计算机的语境里本质其实是这样一个问题给定两个字符串ransomNote和magazine判断magazine中的字符是否能够组成ransomNote并且magazine中的每个字符只能使用一次。这里有两个关键约束很多人读题不仔细就会漏掉第一字符只能使用一次。这不是“只要字符种类出现过就行”而是要求“每个字符的出现次数都要够用”。比如magazine abcransomNote aab字符a在杂志里只出现了一次但要拼两个a这时答案就是false。这道题考的不是“是否存在”而是“数量是否足够”。第二题目明确说了字符串只包含小写英文字母。这一点直接决定了后面用数组模拟哈希表是可行的。如果你是第一次见到这个限定可能感觉这只是一个平凡的条件但等到后面要处理大写字母、数字、中文甚至Emoji的时候你才会意识到这个约束有多重要。可以说这个限定就是整道题选型的钥匙。1.2 两个容易被忽略的边界情况刷题不能只盯着主流程边界条件往往是提交之后才暴雷的地方。这道题有两个边界值得单独说。一个是空字符串。如果ransomNote是空串那么不管magazine是什么都不需要剪任何字母直接返回true。如果两个字符串都为空同样是true。有些人在写的时候不考虑这种情况但只要你的循环逻辑正确空串其实会自动走对不会出错。不过主动把这个问题想清楚写出来的代码会更稳。另一个是长度关系。如果ransomNote.length() magazine.length()那么magazine里的字母总数都不够直接返回false就行。这是一个零成本的剪枝也可以说是短路条件。代码随想录的题解里没有特别强调这个小优化但实际写上并不吃亏尤其是遇到极端测试用例的时候能省掉后面完整的遍历过程。1.3 如果不用哈希表暴力解法到底哪里不行在没有接触哈希表思路之前很多人第一反应是暴力。对ransomNote里的每个字符去magazine里从头到尾找一个匹配的字符找到了就“标记为已用”找不到就返回false。这个思路看起来没问题但有两个致命伤。第一需要一个额外数组来标记某个字符是否已经被用过。如果你不标记同一个字符会被无限次匹配abc都能凑出aaaa这种明显不可能的结果。标记了这个数组之后代码会变得比较啰嗦而且需要维护额外状态。第二时间复杂度是 O(n × m)其中n是ransomNote的长度m是magazine的长度。在最坏情况下两个字符串长度都是10万级别这个双重循环就跑不动了。LeetCode 的测试用例虽然没有刻意卡到爆炸但数据量一大暴力解法很容易超时。暴力解法真正的意义在于它让你直观地感受到这个问题本质上是在反复做“字符是否出现过、出现过几次”的查询。而这类查询恰恰是哈希表最擅长的事情。2. 哈希表的解题逻辑判断“出现过”这件事2.1 哈希表的本质空间换时间哈希表Hash Table这个词听起来很高端但它的核心思想其实一句话就能说清楚为每个可能出现的元素提前准备一个“位置”把“查找”变成“直接取”。举个例子你有一个整数数组想知道数字5在不在里面。最朴素的做法是遍历一遍时间复杂度 O(n)。但如果我提前开一个很大的布尔数组bool exists[MAX_VAL]然后遍历原数组时把exists[arr[i]]置为true那之后判断5是否存在只需要看exists[5]的值时间复杂度直接变成 O(1)。这就是典型的空间换时间。哈希表本质上就是在这个思想上做了推广不要求key一定是整数也不要求key的范围足够小通过一个哈希函数把任意类型的key映射到数组下标。而383这道题由于字符集被限制为26个小写字母我们甚至不需要通用哈希表直接用数组就能模拟出哈希表的效果。2.2 哈希函数与冲突为什么26个字母可以直接映射如果你的key是整数且范围在[0, 25]之间那么最简单的哈希函数就是“什么都不做”把key本身当数组下标。这里小写字母的ASCII码是连续的a到z对应 97 到 122所以magazine[i] - a就能把字符映射到[0, 25]这个区间。这是一个完美的哈希函数没有冲突、计算极快、下标范围可控。之所以专门提“冲突”这件事是因为这是哈希表的核心难点。当两个不同的key映射到同一个位置就发生了冲突需要额外处理。常见的解决办法有链地址法每个桶挂一个链表和开放地址法向后探测空位。C 标准库里的unordered_map用的就是链地址法的思路。但在这道题里因为字符集正好是连续的26个小写字母映射关系是一对一的所以根本不存在冲突。这也是“数组模拟哈希表”能够成立的底层原因当key空间是连续且范围很小的时候数组就是最合适的哈希表。2.3 什么时候选数组什么时候选unordered_map这一条值得单独拿出来讲因为很多人的困惑不是不会写代码而是不知道怎么选数据结构。我的判断标准其实很简单如果key的范围是已知且极其有限的整数区间比如26个字母、128个ASCII字符、10000以内的数字那就用数组。数组的下标天然就是哈希函数的输出查找和修改都是 O(1)没有额外的哈希计算和内存分配常数极小。如果key是字符串、对象、浮点数或者key的范围虽然很大但不确定比如全量Unicode字符那就用unordered_map。它内部会对key计算哈希值处理冲突虽然常数比数组大但胜在通用。有一个很容易被忽略的点数组本质上是一种最朴素的哈希表。很多人学哈希表的时候只记得unordered_map和map却忘了数组也可以承担哈希职责。代码随想录里反复强调“哈希法”并不一定是要你用unordered_map而是在所有能用哈希思想的地方都算。383这道题如果用unordered_map写虽然能过但没有踩到数组这个更优的点上。3. 代码随想录的经典解法数组模拟哈希表3.1 解题流程两次遍历加一次检查代码随想录对这道题的解法是很有标识性的“三步走”逻辑非常清晰第一步遍历magazine把每个字符出现的次数记到一个长度为26的数组里。这一步是在“收集资源”。第二步遍历ransomNote每遇到一个字符就把对应的计数减一。这一步是在“消耗资源”。第三步检查这个数组里有没有负数。如果有负数说明magazine中某个字符的数量不够凑出ransomNote返回false如果全是非负数返回true。第三步的逻辑可以稍微展开一下。计数数组记录的是“杂志里每个字母还剩多少个可用”。拼信的时候用掉一个arecord[0]就减一。如果某个字母被减到负数这就说明你试图使用的次数超过了杂志里实际存在的次数。所以最终检查条件是record[k] 0而不是record[k] ! 0。因为杂志里多余的字母是完全允许的你不需要把每个字母都用上。提示为什么用负数判断而不是直接等于0因为“没用完”是合法的“不够用”才是非法的。负数能精确表达“不够用”这个状态。3.2 完整C代码与逐行注释先给出最基础的版本代码随想录的思路基本就是这个样子class Solution { public: bool canConstruct(string ransomNote, string magazine) { // 记录magazine中每个字符出现的次数 // 因为题目限定只有小写字母所以长度为26就够 int record[26] {0}; // 提前剪枝如果信的长度都比杂志长那肯定凑不出来 if (ransomNote.size() magazine.size()) { return false; } // 第一遍统计magazine里的字符频次 for (int i 0; i magazine.size(); i) { record[magazine[i] - a]; } // 第二遍遍历ransomNote消耗对应字符 for (int j 0; j ransomNote.size(); j) { record[ransomNote[j] - a]--; } // 第三遍检查是否出现负数 for (int k 0; k 26; k) { if (record[k] 0) { return false; } } return true; } };这里有一个很关键但很容易被忽略的细节int record[26] {0};一定要写 {0}。如果只是写int record[26];在C里这是局部变量内容是未初始化的随机值后面所有的和--都是在垃圾值上操作结果完全不可预期。另一个值得注意的地方是magazine[i] - a这个表达式。因为char类型在参与运算时会自动提升为int所以a - a 0z - a 25正好对应数组下标。这个过程不需要强转也不需要额外查ASCII码表写法干净利落。3.3 优化版本边消耗边检查上面这个版本已经可以AC了三遍遍历清楚好懂。但如果你想在常数上再抠一下可以把第二步和第三步合并在遍历ransomNote的时候如果发现某个字符已经减到了负数直接返回false。class Solution { public: bool canConstruct(string ransomNote, string magazine) { int record[26] {0}; for (char c : magazine) { record[c - a]; } for (char c : ransomNote) { if (record[c - a] 0) { return false; } record[c - a]--; } return true; } };这里要注意“先判断再减”的顺序。为什么先判断 0而不是先减再判断 0如果你先执行record[c - a]--再判断record[c - a] 0也是成立的但语义上就没有那么直观先判断“还有没有”有才减没有就直接失败符合人的直觉也避免了让数组出现负数再返工的过程。两种写法都可以时间复杂度都是 O(n m)。我个人在面试和白板题里更倾向用优化版本代码短而且边消耗边判断给人的感觉思路更紧凑。3.4 复杂度分析说下复杂度。设n为magazine的长度m为ransomNote的长度。时间复杂度O(n m)。因为总共就是三趟循环优化版本是两趟每趟都是线性扫描没有任何嵌套。空间复杂度O(1)。这里要特别说一下虽然我们确实开了一个数组但数组长度固定是26不随输入规模变化。输入字符串是1万、10万、100万这个数组都还是26个int所以空间复杂度是常数级 O(1)。这一点也是数组模拟哈希表比unordered_map漂亮的地方unordered_map的空间复杂度虽然理论上也是 O(字符种类数)但因为底层有哈希桶和链表节点实际内存开销远大于一个固定数组。4. 从383扩展到整个哈希表题组4.1 与242. 有效的字母异位词的异同刷题的时候你会发现LeetCode 242和383经常被放在一起讲。两道题都是“统计26个字母频次”但判定逻辑完全不同。242题是判断两个字符串是不是字母异位词要求两个字符串的字符频次完全相等。它的做法通常是遍历第一个字符串时record[s[i] - a]遍历第二个字符串时record[t[i] - a]--最后看整个数组是否全部为0。383题则是判断一个字符串的字符能不能“够”另一个字符串使用它只要求magazine的频次不小于ransomNote的频次。所以最终检查的是“有没有负数”而不是“是否全为0”。用一个生活化的类比来说242问的是“这两篮水果的品种和个数是不是一模一样”383问的是“我手里这篮水果能不能满足你列出来的清单”。前者要求完全对等后者允许有余量。这个区别非常重要因为如果你把242题的“最后检查所有元素为0”直接套到383上就会出错。杂志里多出来的字母会让你以为拼不出来但实际上多余字母根本不影响结果。4.2 从“频次统计”到更多哈希表题目掌握了383其实就掌握了一类题的基本工具字符频次统计。LeetCode 49. 字母异位词分组需要你把所有异位词分到同一组常用的做法就是对每个字符串统计26个字母的频次然后把频次数组转换成一个字符串作为key放入unordered_mapstring, vectorstring。LeetCode 438. 找到字符串中所有字母异位词则是在滑动窗口的过程中不断维护窗口内的字符频次每滑动一次就对比窗口频次和目标字符串频次是否一致。这道题的窗口频次维护本质上还是“数组模拟哈希表 频次增减”的思路。你会发现383这道题虽然简单但它把“哈希映射”“频次统计”“增删检查”这几个动作都过了一遍。后面那些更复杂的题不过是在这几个动作上增加滑动窗口、排序、字符串拼接这些额外操作而已。所以我说别小看这道简单题它是这一整类题的地基。4.3 字符集变大的时候该怎么办如果题目变了字符串不再限定为26个小写字母而是包含大写字母、数字和常见符号那数组就不能只开26了。标准做法是直接开128ASCII码范围然后用record[magazine[i]]或record[magazine[i] - 0]来统计因为ASCII码本身就是连续整数。这里要注意一点ASCII码的范围是0到127所以如果遇到非ASCII字符比如中文UTF-8下每个中文字符占3个字节这种做法就完全不适用了。这种情况下应该改用unordered_mapchar, int来统计。char只是8位而Unicode中的字符数量远远超过256个数组无法覆盖全部可能的key只能靠通用的哈希表来兜底。所以选择数组还是unordered_map本质上就是在问自己一个问题key的取值空间到底有多大、可不可数可数且小数组不可数或超大哈希表。这不是背口诀而是理解原理之后自然得出的结论。5. 刷这道题时我踩过的坑与实测体验5.1 C里数组初始化的坑我第一次写这段代码的时候因为嫌int record[26] {0}太啰嗦自作主张写成了int record[26];。结果前几次运行结果很随机有时候能过样例有时候突然报错完全摸不着头脑。后来才反应过来局部数组不初始化里面全是栈上的随机垃圾值这跟全局数组默认清零是完全不同的行为。这个坑不只是383这一道题会出现所有“数组模拟哈希表”的题都有这个问题。建议刷题时养成习惯凡是涉及计数、标记的数组一律写int record[26] {0};或者用更安全的arrayint, 26 record{};。后者是C11的标准库容器会自动把26个元素全部初始化为0而且越界检查更友好。唯一的问题是有些OJ环境默认C版本比较老可能不支持LeetCode是没问题的。5.2 大小写、非英文字符与空串边界原题说的是ransomNote和magazine由小写英文字母组成这个条件保证了两点一是只有26种字符二是大小写不需要额外处理。网上有些题解为了炫技会处理大写字母和小写字母的转换其实大可不必。题目已经限定死了你再写一堆tolower、toupper转换不仅代码变长反而可能因为误判题目意图而出错。刷题最重要的一件事就是严格遵循题目给出的约束不要自己脑补额外需求。不过话说回来如果你是在本地自测想验证自己的代码能不能“顺便”处理大写字母那也是个好习惯。你可以把数组长度改成128然后用字符直接作为下标不需要减a这样大小写、数字、标点都能统计。实测过就会明白思路和26数组完全一样只是桶变多了。空字符串的情况前面说过这里再提一句就是如果ransomNote为空答案是true不要被“赎金信”这个名字影响觉得必须得拼出点什么才行。5.3 数组 vs unordered_map 的实测差异理论归理论我还是想分享一组实测数据。本地用1e5长度的随机小写字母字符串分别跑“数组哈希”和“unordered_mapchar, int”两个版本重复100次取平均值数组版本单次平均耗时大约0.3毫秒左右。unordered_map版本单次平均耗时大约6到8毫秒偶尔会更高。差距在二十倍左右。这个差距的来源很直观unordered_map要算哈希值要定位桶可能需要分配节点还要处理链表指针。这些操作在单个字符的粒度上都是“额外开销”积少成多之后就被数组版本远远甩开。所以代码随想录在哈希表章节反复强调“能用数组尽量用数组”这句话不是凭空说的是实测出来的结论。尤其当字符集很小且固定的时候数组就是最优解。面试的时候如果你能主动说出来这一点那效果比单纯写出代码要强得多。5.4 给刷题新手的三个建议第一先判断需求再选数据结构。做哈希表题目时先问自己三个问题key是什么key的取值范围有多大需要存多个值还是只标记存在想清楚再动手不然很容易写着写着发现选错容器。第二重点关注循环结束时数组的状态。这道题最后要检查负数、242要检查全零、49要用数组拼key每一步操作完之后数组中每个位置的含义都要清楚。如果自己解释不清说明逻辑还没理顺。第三把送分题的解法变成肌肉记忆。像“26个字母频次统计”这种写法刷完242和383之后应该达到不用思考、顺手就写出来的程度。后面遇到更复杂的字符串题目这些基础代码会帮你节省大量时间。最后说一个我自己的习惯每次刷完像383这样的简单题我都会顺手去代码随想录的题解区和评论区看看别人写的版本。经常会发现很多奇思妙想比如有人用位运算标记字母是否存在有人用unordered_map写出了更通用的解法。多读几种写法再回来思考“这个方案适不适合这道题”这种对比练习对理解数据结构的边界特别有帮助。