企业官网建设流程全解析

• 教程
• 文档
• 知识库

本文以 AlgoNote「算法通关手册」中的 0389. 找不同 题解为主体，完整讲解「在随机重排后的字符串中定位被添加字母」这一经典字符串计数问题：先吃透题目约束与朴素思路，再依次给出哈希表（字典）、定长数组计数、位运算异或、排序共四类解法及复杂度对比，并结合仓库中的哈希表原理、位运算技巧与同类题解源码，帮助读者建立「多重解法 + 复杂度权衡」的刷题方法论。

1. 题目解读

给定两个只包含小写字母的字符串s与t。其中t是由s进行随机重排之后，再在随机位置添加一个字母得到的。

要求：找出字符串t中被添加的那一个字母。

原题解在 find-the-difference.md 中给出的关键信息如下：

• 标签：位运算、哈希表、字符串、排序；
• 难度：简单；
• 输入输出均为字符串，返回值是被添加的单个字符。

由于t比s恰好多一个字符，且多出的字符插入位置随机，因此本题的实质是：在字符多集（multiset）层面求t相对s的差集元素。因为只涉及 26 个小写字母，字符集很小，这为「数组计数」等 O(1) 额外空间的解法创造了条件。

补充说明：题目保证两字符串均由小写字母组成，因此所有解法都可用长度为 26 的定长数组替代哈希表；若题目扩展到任意 ASCII 字符，则哈希表/字典方案的通用性更强。

2. 核心思路：字符频次差值

字符串t比字符串s多了一个随机字母，其余字符与s完全一致（只是顺序被随机打乱）。基于这一点，核心思路非常直观：

1. 统计s中每个字符出现的次数；
2. 遍历t中的每个字符，从s的统计结果中逐一「扣除」对应字符的频次；
3. 当某个字符在s中已被扣完、却在t中再次出现时，该字符就是被添加的多余字母。

这一「频次差值」思想是计数类字符串问题的通用范式，在仓库的同类题解中反复出现：

• 0242. 有效的字母异位词：统计s频次后遍历t逐一相减，出现负数即判定失败；
• 0383. 赎金信：先统计杂志magazine字符频次，再遍历ransomNote消耗频次，频次为 0 即返回False。

3. 解法一：哈希表（字典）统计——原题解主体方案

这是原题解 find-the-difference.md 中给出的标准做法，思路如下：

1. 使用哈希表（Pythondict）存储字符串s中各个字符的数量；
2. 再遍历字符串t中的字符：若该字符在哈希表中存在且计数不为 0，则将其计数减 1；否则说明该字符在s中已经不存在「余额」，即为被添加的多余字母，直接返回。

3.1 完整代码

class Solution: def findTheDifference(self, s: str, t: str) -> str: s_dict = dict() for ch in s: if ch in s_dict: s_dict[ch] += 1 else: s_dict[ch] = 1 for ch in t: if ch in s_dict and s_dict[ch] != 0: s_dict[ch] -= 1 else: return ch

代码要点：

• 第一轮循环用「存在即累加、不存在即初始化」的方式构建频次表，等价于s_dict[ch] = s_dict.get(ch, 0) + 1；
• 第二轮循环的判定条件ch in s_dict and s_dict[ch] != 0与「先判存在、再判计数」的写法等价，可读性更佳；
• 由于题目保证存在唯一答案，循环内必然触发return，无需额外兜底。

3.2 哈希表原理回顾

从 03_06_hash_table.md 可知，哈希表通过「键 key → 哈希函数 Hash(key) → 存储位置」实现 O(1) 平均复杂度的插入与查找。本题中dict以字符为键、频次为值，正体现了哈希表在「按字符统计频次」场景下的核心价值：插入与查找都是平均 O(1)。

该文档还指出，哈希函数设计需尽量均匀分布关键字以减少冲突；Python 内置dict已内置良好的哈希与冲突解决机制（链地址法思想），刷题时可直接使用，无需自行实现。

3.3 复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 为字符串s的长度（t长度为 $n+1$）。两轮线性遍历 + 哈希表平均 O(1) 操作。
• 空间复杂度：$O(|\Sigma|)$，其中 $\Sigma$ 为字符集，本题中 $|\Sigma| = 26$，实际最多存储 26 个键值对，可视为常数空间。

4. 解法二：定长数组计数——更贴近工程实践的优化

由于题目明确限定「只包含小写字母」，可以放弃通用哈希表，改用长度为 26 的定长数组，以字符ord(ch) - ord('a')作为下标。这一写法在仓库同类题解 0383. 赎金信 中已有完整实现可对照：

class Solution: def findTheDifference(self, s: str, t: str) -> str: counts = [0] * 26 for ch in s: counts[ord(ch) - ord('a')] += 1 for ch in t: idx = ord(ch) - ord('a') if counts[idx] == 0: return ch counts[idx] -= 1

对比解法一：

• 内存更可控：数组连续存储，避免dict的哈希表开销（节点、哈希桶、扩容），空间复杂度同为 $O(26) = O(1)$，但常数更小；
• 无哈希冲突：ord(ch) - ord('a')是直接定址，属于 03_06_hash_table.md 中「直接定址法」的典型应用，天然无冲突；
• 前提限制：仅适用于字符集已知且连续的场景（如本题的小写字母），若字符集扩大，数组方案会退化为稀疏数组，此时应回到解法一的字典。

5. 解法三：位运算异或——O(1) 空间的优雅解法

题目标签中包含「位运算」，而仓库 07_06_bit_operation.md 系统讲解了异或运算的规则与性质。异或（XOR）的本质是「相同为 0，不同为 1」，并具有以下三个关键性质（仓库 0136. 只出现一次的数字 题解亦有引用）：

1. 任何数与 0 异或，结果为其自身：$a \oplus 0 = a$；
2. 数与自身异或，结果为 0：$a \oplus a = 0$；
3. 异或满足交换律与结合律：$a \oplus b \oplus a = b \oplus a \oplus a = b$。

5.1 推导过程

将s与t的全部字符按顺序做异或：

• s中每个字符都出现一次；
• t中包含s的全部字符（各一次）加上一个额外字符。

于是每个「正常」字符在总序列中都出现两次，异或后相互抵消为 0；唯独被添加的字符只出现一次，与 0 异或后保留自身。因此对两个字符串全体字符做异或，最终结果就是被添加的字母。

5.2 完整代码

class Solution: def findTheDifference(self, s: str, t: str) -> str: ans = 0 for ch in s: ans ^= ord(ch) for ch in t: ans ^= ord(ch) return chr(ans)

代码要点：

• 将字符先经ord()转为 ASCII 码值再参与异或，最后用chr()还原为字符；
• 两个循环可合并为一个：for ch in s + t:，效果等价；
• 时间复杂度 $O(n)$，空间复杂度 $O(1)$，是四类解法中空间开销最小的一种。

5.3 与同类题的呼应

位运算解法与仓库中 0136. 只出现一次的数字（数组中除一个元素外其余均出现两次）思路完全同构：都是利用「成对元素异或归零、单次元素保留自身」的特性。掌握了本题的异或解法，即可顺带掌握这一类「找落单元素」问题的通用套路；反向地，将字符序列视作「码值数组」，本题即 0136 的字符串版本。

6. 解法四：排序后逐位比较

题目标签同样包含「排序」，这也是一个直观但时间复杂度略高的思路：

1. 将s与t分别按字符排序；
2. 逐一比较对应位置字符，第一个不相同的字符即为被添加的字母；若前面全部相同，则t末尾多出的字符即为答案。

class Solution: def findTheDifference(self, s: str, t: str) -> str: s_sorted = sorted(s) t_sorted = sorted(t) for i in range(len(s_sorted)): if s_sorted[i] != t_sorted[i]: return t_sorted[i] return t_sorted[-1]

• 时间复杂度：$O(n \log n)$，排序开销占主导；
• 空间复杂度：$O(n)$（若使用原地排序的数组可变实现，可降至 $O(1)$）。

该方案可作为面试时的「备用思路」：当面试官追问「能否不用哈希表」时，先给出排序法再过渡到位运算，能体现由浅入深的思维过程。

7. 四种解法对比与选型建议

选型建议：

• 笔试 / 快速 AC：优先哈希表或数组计数，逻辑直观、不易出错；
• 面试加分项：在哈希表基础上主动给出位运算解法，展示对异或性质的掌握（可引用仓库 07_06_bit_operation.md 中的位运算操作总结，如x ^ (x - 1)、x & (x - 1)等技巧）；
• 空间敏感场景：位运算与定长数组均为 O(1) 空间，适合大输入。

8. 刷题延伸与知识网络

本题在 AlgoNote 仓库中的定位如下：

• 题解正文：docs/solutions/0300-0399/find-the-difference.md；
• 章节索引：docs/solutions/0300-0399/index.md（0389 位于 0300-0399 题解段）；
• 分类列表：docs/00_preface/00_06_categories_list.md 中同时归入「位运算题目」与「哈希表题目」分类。

建议按以下路线巩固相关知识：

1. 哈希表基础：先读 03_06_hash_table.md，掌握哈希函数设计（直接定址法、除留余数法等）与冲突解决（开放地址法、链地址法）；
2. 位运算基础：再读 07_06_bit_operation.md，重点理解异或的「相同为 0、不同为 1」及其交换律、结合律性质；
3. 同类题巩固：
   • 0136. 只出现一次的数字：数组版「找落单元素」，异或解法完全同构；
   • 0242. 有效的字母异位词：频次差值 + 负数判定；
   • 0383. 赎金信：定长数组计数的工程化写法；
   • 0268. 丢失的数字：异或思路在「找缺失元素」上的另一应用。

9. 小结

LeetCode 0389「找不同」是一个难度为「简单」、但解法极其丰富的字符串计数题：核心在于抓住「t比s多且仅多一个字符」这一结构特征。原题解 find-the-difference.md 给出了哈希表计数的基础解法；本文在此基础上补充了定长数组计数、位运算异或与排序三类方案，并给出复杂度对比与选型建议。掌握本题，等于同时打通了「频次差值」「直接定址计数」「异或归零」「排序比对」四条技能线，可直接迁移到大量字符串与数组类面试题中。

• 教程
• 文档
• 知识库