★ FEATURED ARTICLE 刷题刷到 383 这道“赎金信”基本是躲不过去的。它被放在哈希表分类里题目短、场景有意思核心就一句话判断字符串 ransomNote 能不能用字符串 magazine 里的字符拼出来而且 magazine 里每个字符只能用一次。难吗上手确实不难但正因为它看起来太简单反而成了最容易踩坑的一块试金石。我见过不少人在这个题上翻车有人把多重集包含关系理解成单个字符的包含关系用 set 就交了有人一上来就写 HashMap完全忽略了题目下面“两个字符串均由小写英文字母组成”这个关键约束还有人能写出固定数组解法但被问到“为什么这题不用哈希表”时就说不清楚了。这篇我就沿着自己当初刷这道题的路径从最暴力的解法讲起一步步演化到 O(n) 时间、O(1) 空间的定长数组版本把每一步的思考过程、代码细节、复杂度和真实遇到的坑都拆开说。适合刚开始刷题准备面试的新手也适合已经能 AC 但想把边界和优化逻辑彻底吃透的同学。1. 题目到底在考什么翻译成“频次子集”问题1.1 先看示例把场景还原题目给了两个字符串ransomNote赎金信和 magazine杂志。要判断赎金信能不能由杂志里的字母拼成规则是 magazine 的每个字母只能用一次。这个设定来源于早期侦探小说里“从杂志上剪字母拼匿名信”的桥段翻译成算法题之后样例长这样ransomNote amagazine b杂志里没有字母 a拼不出来返回 false。ransomNote aamagazine aab杂志里有两个 a 和一个 b能凑出赎金信需要的两个 a返回 true。ransomNote aamagazine ab杂志里只有一个 a赎金信需要两个 a数量不够返回 false。第三个例子是最容易出错的。如果你一看到“判断是否包含”就写set(magazine)那在这个用例上会直接得出 true 的错误结论因为 set 只关心字符有没有出现过不关心出现了几次。题面里那句“每个字符只能用一次”恰恰就是要把你从“集合包含”拉到“多重集合包含”的维度。1.2 核心视角字符频次的子集判断这道题真正的考点是你能不能把“字符串 A 能否由字符串 B 的字符拼出”翻译成“A 的字符频次是 B 的字符频次的子集”。用人话说就是你手里有一堆字母卡片每张只能用一次面前有一张购物清单上面写着需要几个 a、几个 b、几个 c。你要做的不是看一眼货架上有 a 就完事而是逐项核对每个字母的数量够不够。一旦确立了“频次对比”这个视角下一步选什么数据结构就非常清晰了。我们需要一个“字符到次数”的映射表先统计杂志里的每个字符出现次数再在赎金信里逐个扣减。对比的规则是对任意字符 c都要满足杂志里的频次 赎金信里的频次。这一步翻译是整个题目的胜负手想通这一步后面的代码其实只是实现的问题。1.3 和相邻题目的关系这题和“242. 有效的字母异位词”经常被放在一起刷。异位词是要求两个字符串每个字符的频次完全相等赎金信只要求一个方向上的“不小于”也就是说杂志可以有多余字符。如果 ransomNote 和 magazine 恰好是异位词那 ransomNote 一定可以由 magazine 拼出但反过来不一定成立。我建议把这两题连在一起做先做 242 感受“频次相等”的判断再做 383 体会“频次不小于”的判断之后还能接着刷 49 字母异位词分组把字符串频次这条线一次打通。这样比孤立地刷一道题记得牢得多。2. 解法演化从暴力到哈希表再到定长数组2.1 暴力思维先写出来能跑再说我最初想到的方案简单粗暴把 magazine 转成字符列表遍历 ransomNote对每个字符在列表里执行 remove删除失败就说明数量不够返回 false。代码写出来大概是这样def canConstruct(ransomNote: str, magazine: str) - bool: chars list(magazine) for ch in ransomNote: if ch in chars: chars.remove(ch) else: return False return True这个写法思路正确但性能隐患很明显。list.remove()本身要先线性查找再把后面的元素全部往前挪一格外层循环每处理一个字符都要做一次这样的操作。假设 ransomNote 长度为 m、magazine 长度为 n最坏情况下复杂度是 O(m*n)如果每轮还有频繁列表搬移实际开销更大。数据规模一大基本就是超时预警。还有另一种代码量极少的 Python 写法用 count 直接比较def canConstruct(ransomNote: str, magazine: str) - bool: for ch in set(ransomNote): if ransomNote.count(ch) magazine.count(ch): return False return True这套写法在思路上已经贴近“频次子集”了语句也短但每次 count 都要把整个字符串从头到尾扫一遍多个字符重复扫描效率依旧不理想。它适合作为思路讨论出现在对话里真正写提交代码时我不会推荐。2.2 哈希表计数空间换时间暴力法的低效来自反复查找。与之对应的经典思路是第一遍完整遍历 magazine把每个字符的出现次数存进哈希表第二遍遍历 ransomNote每遇到一个字符就把对应计数减一一旦某个计数变成负数就说明杂志里这个字母不够用立即返回 false。def canConstruct(ransomNote: str, magazine: str) - bool: count {} for ch in magazine: count[ch] count.get(ch, 0) 1 for ch in ransomNote: count[ch] count.get(ch, 0) - 1 if count[ch] 0: return False return True这个版本已经能正确通过所有测试时间复杂度 O(mn)空间复杂度 O(K)K 是字符种类数。用哈希表的优势是通用不管字符集是小写字母、ASCII 还是包含中文和 emoji都能处理。缺点是哈希表内部有哈希计算、键值装箱、可能扩容重哈希这些额外开销常数比较大。对这道题来说题目已经明确指出只有小写字母我们其实有更轻、更契合约束的解法。2.3 定长数组读题时最容易忽略的暗示题目描述下方通常会有一行约束“两个字符串都由小写英文字母组成”。这话看着像废话其实是出题人留给你的最优解提示。既然字符集固定为 26 个小写字母那就不需要任何扩展结构直接用长度为 26 的整数数组做计数器即可。下标 0 对应 a下标 1 对应 b以此类推任意字符 ch 的下标可以写成ord(ch) - ord(a)。用数组替代哈希表好处非常直接省掉哈希计算。数组按下标定位是真正的 O(1)且常数极小缓存局部性也好。空间固定为 26 个整数不随输入长度变化是严格意义上的 O(1) 空间。这个“根据字符集大小选择固定数组”的套路在算法题里出现频率极高小写字母用 26 数组ASCII 可见字符用 128扩展 ASCII 用 256。面试时能主动说出这个选择依据比默默写对代码要加分得多。三种解法放一起对比差异会非常直观解法时间复杂度空间复杂度适用场景暴力删除O(m*n)O(n)仅用于思路演示哈希表O(mn)O(K)K 为字符种类数字符集未知或很大定长数组O(mn)O(1)字符集有限且题面已明确3. 数组解法的完整代码与逐行解析3.1 Python 参考实现以定长数组解法为主我给一份可以直接提交的 Python 版本class Solution: def canConstruct(self, ransomNote: str, magazine: str) - bool: if len(ransomNote) len(magazine): return False counts [0] * 26 for ch in magazine: counts[ord(ch) - ord(a)] 1 for ch in ransomNote: idx ord(ch) - ord(a) counts[idx] - 1 if counts[idx] 0: return False return True这里有几个细节值得单独说。第一行长度判断是白送的优化赎金信长度都超过杂志了那必然不可能由杂志拼出来直接返回 false省掉后面所有统计。第一个循环只遍历 magazine把每个字符的频率加进去。ord(ch)拿字符的 ASCII 码ord(a)是 97两者相减得到一个 0 到 25 的整数正好是数组下标。第二个循环里我用了“先扣再看”的写法。为什么不先判断再扣因为我们的目标状态很明确杂志里的频次库被赎金信逐个消耗只要某个计数被扣成负数就说明供不应求立即失败。先扣再看一次操作同时完成了检查动作和状态更新代码也更紧凑。如果先查再扣就得先取旧值、判断、再写回多一步逻辑可读性还没变好。3.2 Java 实现对比Java 版本的结构和 Python 几乎一致但字符串遍历方式稍有区别class Solution { public boolean canConstruct(String ransomNote, String magazine) { if (ransomNote.length() magazine.length()) { return false; } int[] count new int[26]; for (char c : magazine.toCharArray()) { count[c - a]; } for (char c : ransomNote.toCharArray()) { if (--count[c - a] 0) { return false; } } return true; } }Java 里字符相减会自动转成整数所以c - a直接得到下标不需要再调方法。第二个循环的--count[c - a]是“先自减再比较”和 Python 逻辑一样只是写法更紧凑。如果你担心团队里有人读不惯这种前置自减拆成三步也完全等价int idx c - a; count[idx]--; if (count[idx] 0) { return false; }我个人在面试中会先写拆分的版本写完以后补一句“这个其实可以合并成前置自减”既展示代码规范也说明你熟悉语言特性。3.3 C 实现对比C 版本同样很直接class Solution { public: bool canConstruct(string ransomNote, string magazine) { if (ransomNote.size() magazine.size()) { return false; } int count[26] {0}; for (char c : magazine) { count[c - a]; } for (char c : ransomNote) { if (--count[c - a] 0) { return false; } } return true; } };C 里最容易翻车的点就是数组初始化。int count[26] {0};这个写法规定了前 26 个元素全部初始化为 0如果你图省事写成int count[26];那数组里装的是未定义值后续 和 -- 全部建立在垃圾数据上结果完全不可控。这个坑我以前在本地调试时撞到过Debug 模式下内存往往碰巧是 0一切正常一换 Release 就行为异常属于经典的“本地能跑、线上就挂”。如果不想用原生数组vectorint count(26, 0);是更安全的选择只是多了一点动态分配的开销。3.4 优雅但容易背锅的 Counter 一行流Python 选手很流行另一种终极简洁写法from collections import Counter class Solution: def canConstruct(self, ransomNote: str, magazine: str) - bool: return Counter(ransomNote) Counter(magazine)Counter 之间直接用判子集语义恰好就是“左操作数的每个 key 的计数不超过右操作数”。这个写法非常优雅一行搞定日常脚本里我经常用。但如果是面试场景我建议只把它作为补充答案抛出不要作为主代码。原因是面试官极大概率会追问“这行能跑那你能说清它内部做了什么吗”如果你只能答出“这是 Counter 的 magic method”却没有能力写出展开的哈希计数版本反而会扣印象分。另外一个实际问题是性能Counter 底层仍是哈希表创建两个 Counter 需要额外分配、哈希计算常数开销大于固定数组。所以它是“简洁优先”的方案不是“性能优先”的方案。能同时掌握一行流和数组展开版才是完整的能力展示。4. 优化实战缩短路径减少无效工作4.1 长度剪枝代价最低的提前返回最简单也最容易遗漏的优化就是在开始任何统计之前先判断if len(ransomNote) len(magazine): return False这行代码本身是 O(1) 的计算却能直接砍掉最坏情况下的一整轮遍历。假设赎金信长度是 10 万、杂志长度是 9 万没有这行判断时程序照样会先把杂志统计完、再把赎金信扣减一半然后才发现负数。有了这行几乎零成本返回 false。这属于典型的“剪枝”在搜索题里常见在字符串频次题里一样适用。4.2 第二层提前退出扣成负数立即返回定长数组解法里还有一层更隐蔽的剪枝第二遍遍历 ransomNote 时如果中途某个字符把计数扣成负数马上 return false不再继续处理后续字符。这个提前退出不是必须的但它的价值在于当结果本身就是 false 时很多情况下根本不需要读完整条赎金信。时间复杂度从理论上说还是 O(mn) 的最坏情况但平均运行时间会明显下降。比如 magazine 是 abransomNote 是 aaaaaaa 这种反例第二遍循环只要处理到第二个 a 就会返回后面五个字符完全不用看。提示这两个剪枝都基于同一个朴素直觉——别做注定没结果的完整工。写算法题时花一点时间想想“有没有可能在一开始就知道答案”通常能带来意外收益。4.3 用一个小例子手推一遍光看代码不够我习惯把运行过程在脑子里完整跑一遍。拿这个例子magazine aabransomNote aa。初始化 counts [0] * 26。遍历 magazine字符 a下标 0counts[0] 变成 1字符 a下标 0counts[0] 变成 2字符 b下标 1counts[1] 变成 1。遍历 ransomNote第一个 acounts[0] 扣成 1不小于 0继续第二个 acounts[0] 扣成 0不小于 0继续。全部处理完返回 true。再看反例 magazine abransomNote aa。遍历完 magazine 后 counts[0] 1、counts[1] 1。遍历 ransomNote第一个 acounts[0] 扣成 0继续第二个 acounts[0] 扣成 -1小于 0立即返回 false。这个手推过程对新手特别重要。很多人代码写对了但被面试官要求“跑个例子解释一下”时支支吾吾多半就是少了这一步练习。你把这两个例子推演两遍连数组下标的含义都会记得更牢。4.4 复杂度再审视与多语言权衡定长数组解法的时间复杂度第一遍遍历 magazine 是 O(m)第二遍遍历 ransomNote 最坏是 O(n)合起来 O(mn)。加长度剪枝后如果 m n直接 O(1) 返回。空间方面数组长度固定为 26不随输入规模变化所以是严格意义的 O(1)。有人会问都 O(mn) 了还有必要纠结常数吗我的看法是对于这一题常数的意义主要不在运行时差异而在于帮你建立正确的工程直觉。哈希表解法在字符集大的场景是不可替代的但在“字符集固定且已知”的最常见场景固定数组永远更优。语言选择上Python 的 for-each 遍历字符串很方便Java 的 toCharArray 会多一次数组拷贝但可读性好C 直接用 string 遍历也不用担心拷贝。这些细节平时随手注意一下面试时随口说出来显得非常老练。5. 常见问题与排查技巧实录5.1 五个我真实踩过的坑这一题我复盘过很多次也看过别人翻车归纳下来高频错误集中在五个地方。误区一用 set 做包含判断。这是理解层面的错误return set(ransomNote) set(magazine)set 丢了频次信息把“需要两个 a”当成“需要一个 a”。拿 ransomNote aa、magazine ab 一测就露馅。题目里“每个字符只能用一次”这句话就是用来拦截这种错误理解的。误区二先扣减完再统一检查负数。有些同学写成先完整遍历 ransomNote结束后再回头检查 counts 里有没有负值。逻辑上不算错但平白多跑了一段无效遍历还要额外维护状态。相比之下“扣成负数立即返回”这个模式更自然而且在很多频次类题目里都能复用值得养成习惯。误区三下标计算方向写反。ord(ch) - ord(a)和ord(a) - ord(ch)看起来像孪生兄弟实际天差地别。后者会让下标变成负数轻则逻辑错乱重则数组越界。写代码时我会先在注释里写一句“0 代表 a”再动手几乎不会错。误区四C 数组忘初始化。前面已经强调过int count[26] {0};是必写的。原生数组不初始化就是未定义行为很多编译器在 Debug 和 Release 下表现还不一样排查成本极高。误区五忽视长度剪枝。不写长度判断也能 AC因为测试数据未必卡你。但在面试和竞赛里这种零成本剪枝属于基本功的体现。它不改变复杂度的量级却能让你的代码在一开始就排除大量无效计算。5.2 测试用例设计把这些 case 都跑一遍我建议提交前至少覆盖下面这张表里的例子场景ransomNotemagazine预期结果空赎金信true赎金信非空、杂志为空afalse完全匹配abcabctrue杂志数量充足aaaabtrue数量不足aaabfalse杂志有富余字符abcabcddtrue字符完全无关zabcfalse赎金信比杂志长aaaaaaafalse第一行的空字符串容易被忽略。赎金信为空的语义是不需要任何字符即可拼成返回值应该是 true。如果你把后续逻辑写成“遍历 ransomNote如果为空直接跳过”那自然没问题但如果你的代码依赖读取 ransomNote 的第一个字符做判断就可能在边界上出错。这种边界用例本地过一遍比在提交页返工省时间。5.3 面试现场的表达顺序如果面试官现场让你写这题我建议按这条链路走一定先主动确认输入范围。虽然题面已经写明小写英文字母但开口确认“输入是否限定为小写字母”本身就是沟通习惯的加分项。然后用“频次子集”的表述复述需求让对方知道你没有陷入 set 陷阱。接着给两个方案先说哈希表通用性再说数组如何利用字符集约束做到 O(1) 空间并明确说清楚二者只在小字符集前提下等价。写代码时把长度剪枝带上写完不要急着停笔用 ransomNote aa、magazine ab 这个反例走一遍过程最后补一句复杂度分析。我见过不少候选人在这个题上栽跟头其实不是不会写而是把题目当模板背下来了。真正能区分水平的就是你是否理解“频次”而不是“存在性”是否读懂了题面里关于字符集的约束以及能否用一个反例证明你的代码没有逻辑漏洞。把这些点做到这道题就算真正吃透了。最后分享一个我个人的刷题习惯。凡是这类“入门但经典”的题目我都坚持做三件事先写一个笨蛋暴力解感受痛点再用更优的数据结构替换最后拿一个反例在纸上推演一遍。383 恰好把这三步完整覆盖了暴力删除法让我记住重复查找的代价哈希表让我体会空间换时间的思路定长数组则提醒我读题时要留意每一个看似不起眼的约束。这个流程走完这题就不再是一个孤立的答案而是一套可以在字符串频次题上反复套用的方法论。所以如果有人问我刷题热身该从哪道开始我大概率会把这个“赎金信”放到清单最前面。
阅读完成 · 觉得有帮助？
