LeetCode 389. 找不同

2021-12-29 HGNULB 约 8 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 389. 找不同

题意分析

t 是把 s 的所有字符打乱顺序、再额外插入恰好一个字符得到的，要求找出这个多出来的字符。题面里「随机重排」这句话是在明确告诉你：位置信息完全不可靠，唯一可靠的是每个字符出现了多少次。

「恰好多一个」是本题最强的约束。它意味着 t 比 s 只长 1，且除了那一个字符，其余所有字符在两串中的出现次数完全一致。答案是唯一的，不存在多解或无解。

字符集限定为小写字母，长度上限一千量级。字符集小到可以直接用固定大小的容器统计，规模小到线性扫描绰绰有余，但也正因为「只多一个、其余成对」，还存在比统计更省空间的做法。

边界要注意：s 可以是空串，此时 t 只有一个字符，答案就是它；s 中可以有大量重复字符，多出来的那个也可能是 s 里已经出现过的字符（比如 s = "a"、t = "aa"），所以不能用「t 中有而 s 中没有的字符」来判断。

解法：异或抵消

核心思路

直接做法是开一个长度 26 的计数数组：扫描 s 时加一，扫描 t 时减一，最后找到唯一的非零项。这已经是 $O(n)$ 时间、$O(1)$ 空间（字符集大小为常数）。本题还给了更强的条件——t 只比 s 多一个字符，其余字符可以全部成对抵消——因此可以只保留一个异或值。

瓶颈的本质在于「我们记录了太多信息」。计数数组保留了每个字母出现的具体次数，可题目只需要知道「谁的次数是奇数次」——因为除答案外的每个字符都在 s、t 中各出现同样多次，把两串拼起来看，它的总出现次数必然是偶数；只有答案字符的总次数是奇数。

于是关键观察是：把 s 和 t 的全部字符连成一个整体，问题就变成了经典的「找出唯一出现奇数次的元素」。而异或运算恰好提供了这种「成对消失」的能力，它满足三条性质：$x \oplus x = 0$（自反抵消）、$x \oplus 0 = x$（零是单位元）、以及交换律和结合律（顺序无关，正好对应「随机重排」这个条件）。

由此写出算法的不变量：设变量 xor 初值为 0，每读入一个字符就把它的编码异或进去，则任意时刻 xor 等于「到目前为止出现奇数次的字符编码」的异或和。当 s 与 t 的字符全部处理完，成对出现的字符两两抵消为 0，只剩下那个孤立字符，此时 xor 就是答案的 ASCII 编码，强转回 char 即可。

注意这里异或的是字符的编码值而非「是否出现」，所以不需要先减去 'a' 再加回来——直接对 ASCII 值操作，抵消关系同样成立，结果也直接就是那个字符。

解题步骤

用一个 int 变量 xor 初始化为 0。选 0 是因为它是异或的单位元，保证「还没读任何字符」这个初始状态不会污染结果；如果初始化成别的值，最终答案会被额外异或一次那个值而出错。

遍历 s，把每个字符异或进 xor。这一步不做任何判断，因为异或的抵消是自动发生的，我们不需要知道当前字符将来会不会被抵消。

接着遍历 t，同样全部异或进同一个 xor。之所以能共用一个变量而不是分别算再异或，是因为异或满足结合律，$(s_1 \oplus s_2 \oplus \cdots) \oplus (t_1 \oplus t_2 \oplus \cdots)$ 与把所有字符一股脑异或的结果完全相同；两串谁先谁后也无所谓。

把 xor 强转成 char 返回。此时 xor 的值一定落在小写字母的 ASCII 区间内，因为所有其他字符都已抵消为 0，剩下的就是那一个字符本身的编码，不存在高位残留。

以 s = "abcd", t = "abcde" 走一遍。xor 初始为 0。读 s：异或 'a'(97) 得 97；异或 'b'(98)，97 ^ 98 = 3；异或 'c'(99)，3 ^ 99 = 96；异或 'd'(100)，96 ^ 100 = 4。s 处理完 xor = 4。接着读 t：异或 'a'(97)，4 ^ 97 = 101；异或 'b'(98)，101 ^ 98 = 7；异或 'c'(99)，7 ^ 99 = 100；异或 'd'(100)，100 ^ 100 = 0；异或 'e'(101)，0 ^ 101 = 101。循环结束 xor = 101，强转为 char 得到 'e'，正是多出来的字符。

再看一个多出来的字符在 s 中已存在的用例 s = "a", t = "aa"：xor 从 0 异或 'a' 得 97，再异或 t 的两个 'a'，97 ^ 97 = 0，0 ^ 97 = 97，返回 'a'。可见即便答案字符与 s 中的字符重复，奇偶性判据依然成立，这正是「差集」思路会失败而异或不会的原因。

代码实现

// 相同字符两两抵消，最终结果就是多出来的字符。
class Solution {
    public char findTheDifference(String s, String t) {
        int xor = 0;

        for (int i = 0; i < s.length(); i++) {
            xor ^= s.charAt(i);
        }

        for (int i = 0; i < t.length(); i++) {
            xor ^= t.charAt(i);
        }

        return (char) xor;
    }
}

// 相同字符两两抵消，最终结果就是多出来的字符。
func findTheDifference(s string, t string) byte {
	xor := 0
	for i := 0; i < len(s); i++ {
		xor ^= int(s[i])
	}

	for i := 0; i < len(t); i++ {
		xor ^= int(t[i])
	}

	return byte(xor)
}

复杂度分析

时间复杂度：$O(n)$，其中 n 为 s 的长度。凭什么？两个循环分别扫描 s 和 t 各一遍，t 的长度是 n + 1，每个字符只做一次异或这种常数时间的位运算，没有嵌套也没有回溯，总操作数为 2n + 1。

空间复杂度：$O(1)$。凭什么？全程只用了一个 int 变量和一个循环下标，既没有计数数组也没有哈希表，占用与输入规模完全无关。

关键点总结

把「找唯一的落单元素」翻译成奇偶性问题：只要题目保证「除答案外全部成对出现」，就可以用异或把成对的部分自动抹掉。这个模式在「只出现一次的数字」「丢失的数字」「错误的集合」里反复出现，识别它的信号是「其余元素恰好出现偶数次」。

异或的交换律与结合律让顺序无关：本题特意强调 t 是随机重排的，正是为了让依赖位置的做法失效；而异或对顺序免疫，两个串甚至可以交错读取。遇到「打乱顺序」的描述，优先考虑与顺序无关的聚合运算。

只保留需要的信息可以让状态更小：计数数组保留了每个字符的次数，异或只保留所有字符编码的奇偶聚合值。虽然本题 26 个计数槽也是 $O(1)$，异或仍更贴合「恰好多一个、其余完全配对」这一前提。

同类替代方案是求和相减：把 t 的字符编码总和减去 s 的总和，差值就是答案编码。它同样是 $O(1)$ 空间且更直观，但在字符集更大或长度极长时有溢出风险，而异或天然不会溢出。

面试视角：这题几乎必然从「哈希计数」问起，标准的加分路径是主动升级到异或，并说清「因为其余字符总次数为偶数」这个前提。若面试官追问「多出来的是两个字符怎么办」，要能马上答出：异或和退化成两个数的异或，需要按最低位 1 分组求解，这正是「消失的两个数字」的做法。

易错点总结

错误写法：xor 初始化为 s 的第一个字符而不是 0。用例 s = "abcd", t = "abcde" → 首字符 'a' 被多异或了一次，最终结果变成 'e' ^ 'a' = 101 ^ 97 = 4，强转后是一个不可见控制字符，返回值完全不是字母。

错误写法：只遍历 t 不遍历 s，或两个循环写成同一个下标范围。用例 s = "abcd", t = "abcde" → 若把两个循环合并成 for (int i = 0; i < s.length(); i++) { xor ^= s.charAt(i) ^ t.charAt(i); }，t 的最后一位 'e' 根本没被读到，结果是 0，返回空字符。

错误写法：用「t 中出现但 s 中没有的字符」作为判据。用例 s = "a", t = "aa" → 两串的字符集合都是 {a}，差集为空，找不到答案；而正确输出是 'a'。集合丢掉了次数信息，本题必须用次数或奇偶性。

错误写法：先排序两个字符串再逐位比对，但比对循环写成 i < t.length() 且访问 s.charAt(i)。用例 s = "abcd", t = "abcde" → 当 i 走到 4 时 s.charAt(4) 越界抛 StringIndexOutOfBoundsException；正确的写法要以 s 的长度为界，循环走完仍未失配则答案是 t 的最后一个字符。

错误写法：忘记把结果强转回 char，直接返回 int。用例 s = "", t = "y" → Java 中函数签名要求 char，不转会编译失败；即使用 Integer 拼接输出也会打印 121 而不是 y。

错误写法：Go 里对 s[i] 直接异或到 byte 变量并期望处理多字节字符。用例是纯 ASCII 时没问题，但若误以为这套写法能推广到含中文的字符串，s[i] 按字节切分会把一个汉字拆成三段，抵消关系在字节级依然成立但返回类型 byte 无法表示汉字，返回的是残缺字节。本题限定小写字母才安全。

错误写法：用减法版本时把 sum(t) - sum(s) 写反成 sum(s) - sum(t)。用例 s = "abcd", t = "abcde" → 得到 -101，强转 char 后是负值溢出的乱码；t 恒比 s 长，被减数必须是 t。

错误写法：用 26 长度计数数组但索引写成 c 而非 c - 'a'。用例 s = "abcd", t = "abcde" → 首次访问 count[97] 就越界抛 ArrayIndexOutOfBoundsException，数组只有 26 个槽位。

相似题目

题目	难度	考察点
136. 只出现一次的数字	简单	只有一个数组，其余元素严格出现两次，无需跨两个输入拼接
268. 丢失的数字	简单	缺失方向相反，需要把下标 0..n 与数组元素一起异或才能构造出成对关系
260. 只出现一次的数字 III	中等	落单元素有两个，异或和不再是答案，必须按最低位 1 分组后各自求解
242. 有效的字母异位词	简单	只判断两串是否完全同频，答案是布尔值，异或不足以判定需退回计数
645. 错误的集合	简单	同时存在重复与缺失，异或和是两者之差，还需再定位哪一个是重复的