哈希表算法题精讲：从有效字母异位词到频次统计

有一道题我见过不下十次它通常长这样给定两个字符串 s 和 t判断 t 是否为 s 的“有效字母异位词”。别看描述只有一句话里面正好藏着哈希表最核心的用法——用空间换时间把字符出现次数变成可快速查询的键值对。这篇文章我就把“哈希表有效字母异位词”这道题从题目本质、哈希思路、代码实现到边界测试完整拆开讲一遍。无论是准备算法面试还是想弄懂哈希表到底怎么落地都适合往下看。1. 先搞清楚题目在问什么异位词的本质是字母的“多重集合”1.1 题目到底在考什么“有效字母异位词”的英文是 valid anagram翻译成大白话就是两个字符串里的字母种类一样并且每个字母出现的次数也一样只是排列顺序可以完全不同。比如 s anagramt nagaramt 只是把 s 的字母重新洗牌它们互为字母异位词。反过来s ratt car字母集合都不一样自然不算。如果只盯着“字母种类相同”这一点很容易踩进一个误区误以为用集合 Set 就够了。实际上异位词要的是“多重集合”相等也就是英文里常说的 bag。普通集合不关心元素出现几次而多重集合把每个元素出现的次数也作为判断依据。举个例子s aaabt aab。把两个字符串分别转成集合都是 {a, b}看起来集合相等但 s 里有 3 个 at 里只有 2 个 a所以它们不是异位词。这道题表面上是判断字符串实际上考的是三个基本功能否识别“频率统计”这个需求、能否想到用哈希表保存字符到次数的映射、能否正确处理空串和长度不同这类边界条件。只要这三个点理清了代码写起来就是十几行的事。1.2 为什么“排序比较”不是最优解很多初学者看到这个问题的第一反应是把两个字符串排序再比较排完序的结果。代码确实很短比如 Python 里一句return sorted(s) sorted(t)就能跑通。在字符串很短的时候这种写法甚至显得很优雅我当年也这么写过。但排序方案的时间复杂度是 O(n log n)因为每个字符串都要经历一次排序。面试官如果继续追问“能不能做到 O(n)”你就会被卡住。更严格地说排序还会产生额外的临时数组或新字符串空间上也不是最省的。这时候哈希表的优势就体现出来了遍历一次 s把每个字符出现的次数记下来再遍历一次 t把对应的次数减掉。整个过程只跟字符串长度 n 相关时间复杂度 O(n)用空间换取时间正是哈希表最经典的用法。2. 用哈希表统计词频从两张表退化到一张表2.1 先加后减的核心思路解决异位词最直接的哈希思路是“频次抵消”。第一遍遍历 s遇到一个字符就给对应的计数加 1第二遍遍历 t遇到一个字符就给对应的计数减 1。如果到最后所有字符的计数都归零说明 t 里每个字符的出现次数和 s 完全一致只是顺序不同。这里有一个值得养成习惯的设计选择用一个哈希表而不是两个。有些同学会先分别统计 s 和 t 生成两张计数表再比较两张表是否相等。这样可以但会多占用一份哈希表的空间而且必须等第二张表完整生成后才能比较没法提前终止。如果只有一个哈希表遍历 t 时一旦发现某个字符的计数已经变成 0却还要再减一次说明 t 中该字符的数量超过了 s可以立刻返回 False不用继续遍历。这种“提前拒绝”在输入很长时能省下不少时间。用伪代码描述主流程就是如果 s 和 t 长度不同直接返回 False 初始化一个空哈希表 counts 遍历 s counts[ch] 1 遍历 t counts[ch] - 1 如果 counts[ch] 0 返回 False 返回 True这个流程里有三个容易被忽略的细节。第一长度检查必须放在最前面因为如果长度不同两个字符串必然不可能是异位词。第二第一遍遍历用ch not in counts之类的判断来初始化缺失键。第三第二遍遍历不能只检查“键是否存在”还要检查“减完之后是否为负数”因为“存在但数量不够”也是失败。2.2 Python 实现细节与 Counter 的正确用法Python 里最朴素也最适合面试现场写的版本是用普通字典def is_anagram(s: str, t: str) - bool: if len(s) ! len(t): return False table {} for ch in s: table[ch] table.get(ch, 0) 1 for ch in t: if ch not in table: return False table[ch] - 1 if table[ch] 0: return False return Truetable.get(ch, 0) 1是处理“键不存在”时最常用的写法如果 ch 还没出现过就按 0 加 1如果出现过就取出旧值加 1。第二个循环里先判断ch not in table是为了避免出现 t 中独有的字符因为这种字符在 s 里出现次数为 0直接减下去会变成负数逻辑上虽然也能被负数判断拦下来但显式判断更清晰。如果你在写日常脚本而不是面试代码Python 的collections.Counter可以一行搞定from collections import Counter def is_anagram(s: str, t: str) - bool: return Counter(s) Counter(t)Counter本质上就是一个专门计数的哈希表它比较相等时会把缺失的键当成 0 处理所以Counter(aab)和Counter(abb)会被正确判断为不相等。我确实会在自己的工具脚本里用这种写法因为它最不容易出错。不过面试时我建议还是手动实现一次否则面试官很难判断你是真的懂哈希表还是只是知道有个 Counter 类。2.3 JavaScript 里用 Map 还是普通对象JavaScript 的对应实现有两个选择Map和普通对象{}。我强烈建议用Map原因是普通对象有一些跟“原型链”相关的坑。先看用Map的版本function isAnagram(s, t) { if (s.length ! t.length) return false; const counter new Map(); for (const ch of s) { counter.set(ch, (counter.get(ch) || 0) 1); } for (const ch of t) { const current counter.get(ch); if (current undefined) return false; counter.set(ch, current - 1); if (counter.get(ch) 0) return false; } return true; }这里counter.get(ch) || 0利用了“undefined 是假值”的特性代码简洁。第二个循环中current undefined用来判断 t 中是否存在 s 里没有的字符undefined表示完全没出现过。为什么不推荐普通对象因为对象有原型链如果字符串里出现__proto__、constructor、toString这类特殊键很容易读到原型上的属性导致计数逻辑被污染。比如counter[toString]会拿到一个函数而不是 undefinedcounter[ch] || 0的结果就完全不对了。用Map可以彻底避开这个坑因为Map的键是干净独立的不继承任何东西。如果你的环境必须用普通对象至少也请使用Object.create(null)创建一个没有原型的对象否则不要拿对象字面量直接当通用字符哈希表。3. 限定小写字母时用定长数组替代哈希表3.1 数组的 O(1) 空间是怎么来的很多版本的题目会在描述末尾加一句假设 s 和 t 只包含小写字母。这句话看起来不起眼实际上是把题目从“通用哈希表”直接降级成“定长计数数组”的信号。因为小写字母只有 26 个我们可以准备一个长度为 26 的整数数组下标 0 对应 a下标 25 对应 z。这个数组本质上是一个“哈希函数被固定下来”的哈希表字符经过ord(ch) - ord(a)的换算映射到 0 到 25 之间的一个桶。由于桶的数量是固定的 26空间复杂度是 O(1)而不是随输入字符种类增长。从性能角度看数组比通用哈希表有两个明显优势。第一数组下标访问是 O(1) 且常数极小不需要计算哈希散列也不需要处理冲突。第二26 个整数在内存里是连续排列的CPU 缓存命中率高。在只含小写字母的约束下这是最优实现。用 Python 写出来是这样def is_anagram(s: str, t: str) - bool: if len(s) ! len(t): return False counts [0] * 26 for ch in s: counts[ord(ch) - ord(a)] 1 for ch in t: idx ord(ch) - ord(a) counts[idx] - 1 if counts[idx] 0: return False return Trueord返回字符的 Unicode 码点。小写字母 a 到 z 在 ASCII/Unicode 表里是连续排列的所以ord(b) - ord(a)正好等于 1ord(z) - ord(a)正好等于 25。用ord(a)而不是硬编码 97可读性和可维护性都好很多。3.2 字符到索引ord 与 charCodeAt 的边界JavaScript 里对应的换算函数是charCodeAt同样基于连续编码的特性function isAnagram(s, t) { if (s.length ! t.length) return false; const counts new Array(26).fill(0); for (let i 0; i s.length; i) { const idx s.charCodeAt(i) - 97; counts[idx] 1; } for (let i 0; i t.length; i) { const idx t.charCodeAt(i) - 97; counts[idx] - 1; if (counts[idx] 0) return false; } return true; }这里我用97而不是a.charCodeAt(0)只是因为 JavaScript 里每次调用charCodeAt都有额外开销把差值直接写成 97 在热路径上会稍微快一点。当然如果追求可读性先定义const aCode a.charCodeAt(0)再减也是更好的做法。这个版本最大的风险是输入越界。如果字符串里混进了大写字母比如A的码点是 65减掉 97 后会得到 -32。JavaScript 数组访问counts[-32]不会直接报错它会像访问普通对象属性一样返回 undefined然后undefined 1会得到 NaN整个判断直接失序。如果是 Pythoncounts[-32]甚至真的会从数组末尾开始取数结果更是离谱。所以数组方案的前提是“输入范围必须被题目保证”否则就老老实实回到哈希表或先做归一化处理。4. 边界条件与反直觉测试空串、长度、大小写、Unicode4.1 长度检查是最廉价的剪枝我在给别人讲这道题时最喜欢问一个问题第一行代码应该写什么答案是长度检查。两个字符串如果长度都不一样无论如何也不可能有相同的字符频次。长度检查看起来简单但它同时起到了“剪枝”和“简化后续判断”的作用。在手动哈希表版本里如果 s 和 t 长度相等那么第一遍遍历写入 s 的频次第二遍遍历 t 后只要过程中没有出现计数为负最终的哈希表一定全部归零不需要再额外遍历一遍表确认。反例是如果不做长度检查第二遍遍历完 t 后可能哈希表里还残留着几个正数但代码已经return True了这就会出错。所以必须用len(s) ! len(t)提前拦住让后面的逻辑保持在“长度相等”这个前提之下。4.2 计数器出现负数提前拒绝在第二个循环里counts[ch] 0的判断是最容易漏掉的一行。很多人只写完减一操作就结束循环最后返回 True然后被测试用例 aab 和 abb 卡住。解释一下为什么会出现负数s aabt abb长度相同都是 3。遍历 s 后哈希表是 {a: 2, b: 1}。遍历 t 时第一个字符 a 让 a 变成 1第二个字符 b 让 b 变成 0第三个字符 b 再次递减b 就从 0 变成了 -1。此时已经可以确定 t 里 b 的数量比 s 多继续遍历没有任何意义直接返回 False。负数判断看起来只是一个小优化但它实际上改变了算法的行为它让算法具备了“流式失败检测”的能力。这也是为什么我推荐“一张表先加后减”而不是“两张表最后比较”的原因之一后者必须完全处理完所有字符才知道结果没法中途退出。4.3 大小写、空格、多字节字符的真实表现我整理过一批用于自测的典型用例你可以直接拿去验证自己的实现输入 s输入 t预期结果说明true两个空串互为异位词afalse长度不等anagramnagaramtrue经典正例ratcarfalse普通失败用例aababbfalse字母相同但数量不同abbatrue简单重排这里有一个很多人没意识到的坑大小写。题目如果没说明忽略大小写那么A和a就是两个完全不同的字符。在只含小写字母的题目假设下不用管但如果输入可能包含大写字母你需要先问面试官“大小写敏感吗”如果要统一可以选择在遍历前调用s.lower()和t.lower()但这会额外生成新字符串空间上不是免费的。空格同理。hello world 和 world hello 如果把空格计入频次它们是异位词但很多场景下空格应该被忽略。这种问题没有标准答案关键是在动手前把输入规则确认清楚。Unicode 字符也是一个容易出问题的点。Python 的for ch in s默认按 Unicode 码点遍历所以中文、日文、甚至 emoji 都能正确处理例如你好和好你用通用哈希表版本判断会返回 True。JavaScript 则要小心使用for...of遍历字符串时按码点迭代能正确处理代理对但如果你用s[i]或charCodeAt(i)去遍历遇到 emoji 这类超出基本多语言平面的字符时会被拆成两个独立的码元计数结果会出错。应对方法是用for...of或先Array.from(s)转成数组。5. 从一道题看一类题哈希思想如何迁移到异位词分组5.1 分组场景下的哈希键选择“有效字母异位词”只是异位词问题里最基础的一个它稍微升级一下就变成另一个经典问题给一组字符串把互为异位词的字符串放到同一个组里。例如输入[eat, tea, tan, ate, nat, bat]希望输出[[eat, tea, ate], [tan, nat], [bat]]。解决思路本质上还是哈希表只是哈希表的键从“单个字符”变成了“字符串的频次指纹”。有两种常用选键方式。第一种是排序键把每个单词排序后作为键。eat和tea排序后都变成aet所以它们会被分到同一个桶里。实现很短def group_anagrams(words): groups {} for word in words: key .join(sorted(word)) groups.setdefault(key, []).append(word) return list(groups.values())第二种是计数键用一个长度为 26 的计数数组记录每个字母出现次数再把这个数组转成元组作为键。eat和tea的计数元组完全一样所以会被分到同一个桶里。def group_anagrams(words): groups {} for word in words: counts [0] * 26 for ch in word: counts[ord(ch) - ord(a)] 1 key tuple(counts) groups.setdefault(key, []).append(word) return list(groups.values())可以看到只要能设计出一个稳定、可哈希的“指纹”哈希表就能把看起来无序的问题转换成“按桶归类”的问题。这和判断两个字符串是否互为异位词是同一种思维指纹相等就属于同一个异位词类别。5.2 复杂度与内存放大的取舍排序键和计数键各有取舍。排序键的时间复杂度是 O(k log k)其中 k 是单词平均长度计数键的时间复杂度是 O(k)因为只需要遍历一次单词统计频次。在单词较长、数量较多时计数键更优。空间上排序键只需要多存一个排序后的字符串通常比 26 个整数的元组更省尤其当单词很短时。计数键则固定产生一个长度 26 的元组无论单词多短都要占这么多空间。我做这类题目时会先看数据范围再选方案。如果单词数量多、长度长选计数键如果单词普遍很短且要求代码简洁排序键完全够用。其实这跟“有效字母异位词”里选哈希表还是数组的道理一样没有绝对最优只有对当前约束最合适的方案。6. 面试实战这道题的最佳展示顺序与踩坑复盘6.1 先讲思路再写代码这道题我在模拟面试里给人讲过很多次最让我着急的不是写不出代码而是上来就闷头写。正确的打开方式是先和面试官确认几个关键点字符串里只有小写字母还是包含任意 Unicode 字符大小写是否敏感空格是否计入时间和空间分别最看重哪个第一问直接决定你要不要用定长数组。如果面试官说“只含小写字母”那数组版本就是最好的答案因为你可以顺势解释 O(1) 空间。如果面试官说“不限字符集”那就要用哈希表并且可以提到Map和普通对象的区别。第二问是在测试你的需求分析能力很多真实业务问题就坏在“假设不明确”。第三问则是引导你主动分析复杂度而不是等面试官追问。先讲清“长度检查 频次统计 先加后减”这三个步骤然后再写代码整个过程会顺畅很多。6.2 现场写码时的三个检查点写代码时我习惯写完先做三遍自查第一长度检查是否在函数最前面。这行漏掉后面所有逻辑都可能要额外兜底。第二下标换算是否安全。用数组版本时要确认输入真的只有小写字母否则ord(A) - ord(a)会得到负数。用哈希表版本时要确认用的不是普通对象来处理特殊键。第三第二遍遍历时是否检查了负数和缺失键。if ch not in table管住“完全没出现过”if table[ch] 0管住“出现过但数量不够”两者搭配才完整。写完代码后别急着说“好了”自己先拿(anagram, nagaram)和(rat, car)两个用例快速过一遍。这个小习惯在面试里很加分。6.3 我的复盘体会我自己复盘这道题时最大的感受是哈希表并不神秘它就是“把需要反复查找的信息提前按某种规则放到一个能快速定位的位置上”。有效字母异位词里的字符频次就是这种需要反复比对的信息。排序方案代码短但哈希表方案在时间上更优哈希表通用但数组在小写字母场景下更极致。到底选哪个取决于你对输入约束的理解。这道题能讲的东西其实比它看起来多得多哈希结构选型、复杂度权衡、边界条件、代码可读性全都藏在短短十几行里。把这题吃透后面遇到任何“频率统计”相关的问题你都会比别人多想一层。