1. 先想清楚异位词判断的本质是什么最近刷 LeetCode Hot 100 榜单49. 字母异位词分组 让我特别想写一篇 Go 语言题解。题目本身不难但解法里藏着一个很值得琢磨的点Go 的数组可以直接当作 map 的哈希键。很多人看到这道题第一反应是“先排序再分组”这当然能过但如果你对 Go 的类型系统足够熟悉会发现还有一个更干净的选择——把 26 个字母的出现次数统计进一个[26]int数组再把数组整体当作 key。这篇文章就从这里切入把题目拆开讲清楚暴力解为什么慢、排序解哪里不够高效、数组键为什么更符合 Go 语言习惯最后再用边界用例、面试追问和同类题收尾。适合正在刷 Hot 100 的 Go 学习者也适合想搞懂 map 键约束的读者。1.1 题面与示例先明确“字母异位词”到底指什么题目给一个字符串数组例如[eat, tea, tan, ate, nat, bat]要求把字母异位词组合在一起。字母异位词的定义很简单两个字符串包含的字母种类和数量完全相同只是排列顺序不同。比如eat、tea、ate都含一个e、一个a、一个t它们就是一组tan和nat是一组bat找不到同伴单独成组。这个定义里其实藏着两种判定思路。第一种是排序视角把字符串内部排序排序后相同的字符串就是异位词。eat排序后是aettea排序后也是aet于是它们可以归为一组。第二种是计数视角统计每个字母出现的次数得到一份“频率清单”。eat和tea的频率清单都是a:1, e:1, t:1所以它们等价。排序视角靠的是“内容一致”计数视角靠的是“次数一致”本质上是一回事。你写代码时只需要选一个方向。但选哪个方向会直接影响代码的复杂度和可读性这也是这篇文章后面要展开的重点。1.2 暴力解法与瓶颈为什么不能两两比较硬判断不扯远先看最朴素的思路。遍历字符串数组把每个字符串和已有分组的第一个字符串做比较判断它们是不是字母异位词是就放进那组不是就新开一组。判断两个字符串是否互为异位词可以再套一层循环统计字数。假设数组长度为 N字符串平均长度为 K整体时间复杂度是 O(N²K)。我给一个直观数字如果 N 是 5000、K 是 100暴力判断需要做大约 25 亿次字符统计这在在线评测环境里几乎跑不满时间限制。暴力解的意义在于帮我们确认一个方向两两比较是低效的必须把“比较”变成“查字典”。也就是说给每个字符串算出一个统一的键值让互为异位词的字符串命中同一个键再把这个键挂到 map 的桶上去。接下来的问题只是用什么样的键最自然、最高效2. 巧用数组作哈希键从语言特性到算法设计2.1 Go 的 map 键约束为什么数组可以切片不行Go 语言对 map 的 key 有一个硬性要求key 的类型必须支持和!运算。基本类型、指针、channel、接口、结构体都可以数组也可以。切片不行。很多 Go 新手在这里栽过跟头写map[[]int][]string直接编译报错提示invalid map key type []int。原因要从底层讲起。切片是引用类型它包含一个指向底层数组的指针、长度和容量三个字段两个切片哪怕内容完全一样也不能用直接比较切片只能和nil比较。而数组是值类型[26]int和[26]int可以逐元素比较所以它能合法地成为 map 的 key。换句话说数组天然适合做“指纹”因为它的内容就是它的身份。这就是“巧用数组作哈希键”的语言基础。2.2 一个 [26]int 数组恰好就是异位词指纹题目额外限制了一个关键条件字符串只包含小写字母。这句话很多人扫一眼就过去了但它决定了我们可以用固定长度数组做频次统计。小写字母一共 26 个用一个[26]int数组每个位置代表一个字母从a到z的出现次数就能完整描述字符串的组成。把eat统计一遍得到[1,0,...,1,1,...]把tea、ate统计一遍得到的是同一个数组。这些字符串共享同一份“频率指纹”所以它们在 map 里会命中同一个键。真正妙的是在大多数语言里你想直接拿数组当哈希键要么需要重写 hashCode要么需要先把数组序列化成字符串而 Go 中[26]int本身就可以直接作为 map 的 key连序列化的代码都不用写。2.3 为什么比“排序后字符串键”和“频次拼接键”更舒服写这道题常见的三种键方案可以放到一起对比。键方案核心操作时间复杂度优点缺点排序后字符串对单词排序转 stringO(NK logK)直观、跨语言通用排序开销大字符串拷贝额外耗内存频次拼接字符串统计次数后拼成 #1#0#2O(NK)不受限于固定字符集中间字符串分配多代码绕[26]int 数组键统计次数后直接用数组O(NK)代码最简洁效率稳定必须知道字符集范围排序键版本很容易写但有一个隐性成本每个字符串都要做一次 O(K logK) 的排序排序完成后还要把[]byte转成string才能当 key。频次拼接键虽然省了排序但需要手动拼#1#0#2这种字符串人为引入了格式解析问题。数组键几乎没有额外成本[26]int固定 208 字节Go 对它做哈希时按连续内存逐段计算速度非常稳定。我个人在本地实测时数组键版本通常比排序键版本快一截尤其当字符串比较长的时候节省的排序时间非常可观。所以这道题在 Go 里用数组键不是炫技而是更符合语言习惯的高效写法。3. 完整题解两种 Go 实现与关键细节3.1 排序键版本容易想到的入门写法先写一个最标准的排序键版本方便对照import sort func groupAnagrams(strs []string) [][]string { m : make(map[string][]string) for _, s : range strs { bs : []byte(s) sort.Slice(bs, func(i, j int) bool { return bs[i] bs[j] }) key : string(bs) m[key] append(m[key], s) } res : make([][]string, 0, len(m)) for _, v : range m { res append(res, v) } return res }这段代码没有错误但每次循环都要对一个字节切片调用sort.Slice底层使用快速排序平均成本是 O(K logK)。此外[]byte(s)本身也会产生底层数组拷贝string(bs)又可能触发一次拷贝。对 Hot 100 的数据量来说能过但确实不够优雅。3.2 数组键版本推荐的核心实现再看数组键版本核心逻辑几乎只有一半func groupAnagrams(strs []string) [][]string { m : make(map[[26]int][]string) for _, s : range strs { var key [26]int for i : 0; i len(s); i { key[s[i]-a] } m[key] append(m[key], s) } res : make([][]string, 0, len(m)) for _, v : range m { res append(res, v) } return res }var key [26]int声明了一个全零数组Go 会自动把 26 个 int 初始化为 0这正好是频次统计的起点。内层循环用s[i]拿到字符串第 i 个字节s[i]-a把字母映射到 0 到 25 的索引每出现一次就给对应位置加 1。统计完毕的key直接作为 map 的键append后的结果再写回m[key]。最后遍历 map 收集分组即可。3.3 代码里几个容易翻车的细节第一次写这个版本的人最容易在下面几个地方出问题。第一不要把var key [26]int写成key : []int{}。后者是切片切片不能当 map 的 key编译器直接拒绝。第二append(m[key], s)必须把结果重新赋值给m[key]。m[key]本身是[]string切片append如果触发扩容会返回一个全新的切片头你不写回 map数据就可能丢。第三for i : 0; i len(s); i拿到的是bytefor _, ch : range s拿到的是rune。这道题小写字母纯 ASCII两者都能正确计算索引但如果字符串里出现中文或多字节字符ch-a可能会越界。LeetCode 本题明确限定小写字母所以用哪种遍历都行但搞清楚区别总没有坏处。第四返回结果时用make([][]string, 0, len(m))预先分配容量可以省掉多次扩容。这个优化虽然细微在面试里说一句会显得你注意性能细节。4. 复杂度分析、正确性证明与边界用例4.1 时间复杂度与空间复杂度数组键版本的时间复杂度是 O(NK)N 是字符串数量K 是字符串平均长度。每个字符串只需要遍历一次做频次统计map 的写入和查询在 key 长度固定为 26 个 int 的情况下哈希计算成本是常数级。空间复杂度是 O(NK)因为 map 和最终结果都要保存所有原始字符串。排序键版本的时间复杂度是 O(NK logK)主要差在排序。如果 K 比较小两者差距不明显一旦 K 变大比如字符串平均长度达到 200排序的开销就会被明显放大。4.2 边界用例与手算验证拿题目示例[eat, tea, tan, ate, nat, bat]走一遍eat统计后 key 是a:1, e:1, t:1tea统计后 key 也是a:1, e:1, t:1tan统计后 key 是a:1, n:1, t:1ate落入eat那组nat落入tan那组bat的 key 是a:1, b:1, t:1没有同伴最终输出[[eat,tea,ate], [tan,nat], [bat]]题目允许分组顺序任意所以正确。还要考虑几个容易被忽略的边界情况strs []空字符串统计后是全零数组自己成组结果是[[]]。strs [, ]两个空字符串共享全零 key归到同一组。从定义看空字符串由零个字母组成彼此当然是“异位词”。strs [a]单个字符也能正常分组。strs [ab, a]不同长度的字符串频率数组必然不同不会错误分到一组。4.3 正确性证明可以说清楚的两句话这道题的正确性本质上来自一个充要条件两个字符串互为字母异位词当且仅当它们的 26 个字母频次数组完全相同。如果互为异位词每个字母出现次数相同数组必然相等反过来如果数组相等说明两个字符串由完全相同的字母集合组成必然可以通过重排列得到所以互为异位词。map 把数组相等的字符串放到同一个键下面分组自然不重不漏。5. 面试场景把 Go 特性讲成亮点而不是背答案5.1 思路陈述的顺序很关键面试时如果直接甩出数组键版本面试官可能觉得你在背题。更好的节奏是先讲暴力解点出 O(N²K) 不可行再讲排序键说明能优化到 O(NK logK)最后话锋一转指出在 Go 里可以利用数组可比较的特性用[26]int直接作为 key把复杂度降到 O(NK)。这样层层递进既能展示算法分析能力又能展示你对 Go 类型系统的理解。具体话术可以这样说“这道题我倾向于用计数数组。因为题目限定小写字母我统计每个字符串的 26 个字母出现次数得到一个 [26]int。在 Go 中数组是值类型且可以比较所以我可以直接用这个数组作为 map 的 key而不需要把它转成字符串这样比排序快一个 log 因子。”5.2 高频追问和应对方式面试官大概率会追问几个点提前准备好能镇住场。追问数组为什么能作为 map 的 key回答Go 要求 key 类型可比较数组是值类型内容可以通过 逐元素比较切片是引用类型不能比较所以不能作为 key。追问如果字符集不只有小写字母怎么办回答可以扩大数组长度比如 [256]int 覆盖 ASCII或者使用 map[byte]int 动态统计再把结果编码成字符串作为 key。追问[26]int 作为 key哈希开销会不会很大回答固定 208 字节Go 运行时按连续内存计算哈希常数级开销通常比字符串拷贝和排序更省。追问能不能不用 map 完成分组回答可以把每个字符串的 key 求出来对 (key, 原始字符串) 排序相同的 key 自然连续再切分成组。可以不用 map但实现更繁琐。追问遍历字符串时 byte 和 rune 有什么区别回答下标访问 s[i] 得到 byterange 得到 rune本题全 ASCII 小写字母都可以但要清楚边界。6. 从这题延伸开的 Go 基础与同类题型6.1 数组和切片值得反复强调的 Go 语言差异这道题其实是一个很好的 Go 基础案例。数组的长度是类型的一部分[26]int和[27]int是两个完全不同的类型。声明var a [26]int后26 个元素自动为零值这正好让频次统计从零开始。切片没有长度信息底层是引用语义所以既能动态扩容也不能直接作为 map key。很多 Go 入门教程会单独讲“数组初始化”“二维数组”“数组和切片的区别”但学完就忘。通过 LeetCode 题来理解这些概念印象会深得多。下次你看到别人用make(map[string][]string)做字母异位词分组完全可以在心里换算成数组键写法这种“语言特性驱动算法设计”的感觉是单纯刷题很难获得的。6.2 同一套路的姊妹题242、438、567这个技巧不是只属于 49 题。242 题“有效的字母异位词”只需要比较两个字符串的频次数组是否相等438 题“找到字符串中所有字母异位词”需要在长串上维护一个滑动窗口窗口内的频次数组和目标字符串频次数组一致时就记录起始下标567 题“字符串的排列”思路和 438 基本一致。这三道题都是[26]int 频次统计的组合熟练掌握后可以举一反三。6.3 我刷这道题时踩过的几个坑最后分享几个真实教训。我第一次实现时想当然地用了map[[]int][]string编译直接报错才意识到切片不能当键。后来改成[26]int通过了但又写成了for _, ch : range s { key[ch-a] }字符串一长我没想清楚 rune 的语义幸好小写字母不会越界。还有一次我漏了把append结果写回 map本地测试时发现明明加了字符串分组却消失了一部分排查了半天才意识到是切片扩容后没有被 map 持有。如果你也准备用这道题练习 Go我的建议是先用数组键版本跑通再主动把[26]int换成排序键写法然后对比两种实现的性能差异。你会发现语言特性用对了代码是真的可以又短又快的。