链接：https://leetcode.cn/problems/find-the-difference/description/
题目
简单来说 t 是由 s 随机重排，并添加一个字母而来的，那么已知：
- t 的长度比 s 的长度大，并且为 1
- s 和 t 中存在的字母数量 除了 t 新增的字母，其他都是一致的
解法一
思路
通过使用 哈希表，通过对两个字符串的字符索引（规则：字母 - 'a'；例如：b，那么索引就为 1）分别进行哈希表计数，最终对比两张哈希表中的数量，数量不同，则说明当前索引对应的字母就是 t 新添加的字母
因为 s 和 t 的范围为 26个小写字母，那么直接通过 int 数组去模拟哈希表即可，例如：'a' 就代表数组索引 0，'b' 就代表数组索引 1
代码
/** * 执行用时分布 2 ms 击败 67.07% 消耗内存分布 42.42 MB 击败 62.25% * 利用 哈希表 字符计算找不同，只要两张 哈希表 的数量不同，则当前下标 + 'a' 就能得到添加的 字母 */ public char findTheDifference(String s, String t) { // s 为空（s.length = 0），那就说明 t的长度为1，并且就是答案 if (s.isEmpty()){ return t.charAt(0); } // 因为 t 为 s 的随机重排，所以需要计数，才能知道新增的 字母是哪一个 // 定义两个数组用于存放对应字母有多少个 int[] sMap = new int[26]; int[] tMap = new int[26]; // 遍历 s 和 t for (int i = 0; i < s.length(); i++){ // s 下标 = 字母 与 'a' 的 Unicode 码点距离（a 到 z 是按顺序的），例如：'b' - 'a' = 1 int sIndex = s.charAt(i) - 'a'; sMap[sIndex]++; // 等同于上面，只是换种写法 tMap[t.charAt(i) - 'a']++; } // 因为 t 少遍历了一次，所以这里再进行处理 tMap[t.charAt(t.length() - 1) - 'a']++; // 对比 sMap 和 tMap 的数量，就能找出不同 for (int i = 0; i < 26; i++){ // 数量不相同，代表找到了不同，直接返回即可 if (sMap[i] != tMap[i]){ return (char)('a' + i); } } // 不可能走到这里，因为上面已经遍历完了，返回 'a'，只是因为不能返回空 return 'a'; }
解法二
思路
既然 t 字符串中的字母除了新增加的 字母，其余的都与 s 一致（排除字母随机重排的因素），那么就可以将 两张哈希表缩少为 一张哈希表。
每当遍历 s 和 t 字符串的一个字母时，s 出现的字母，哈希表对应的数组索引 减一，t 出现的字母，哈希表对应的数组索引 加一。遍历结束后，哈希表中只有一个值为 1，其他为0。
最终遍历哈希表，如果值为 1，直接返回对应的字母即可
代码
/** * 执行用时分布 2 ms 击败 67.07% 消耗内存分布 42.14 MB 击败 97.27% * 使用 哈希表，并对 s 和 t 字符串对应的字母，进行抵消的方式，最终只要哈希表中索引不为 0，就是 t 字符串新增的字母 */ public char findTheDifference(String s, String t) { // 使用 数组 模拟哈希表 int[] map = new int[26]; // 遍历 s 和 t for (int i = 0; i < s.length(); i++){ // s 对应的字母，就往 哈希表中对应的索引 减 1 map[s.charAt(i) - 'a']--; // t 对应的字母，就往 哈希表中对应的索引 加 1 map[t.charAt(i) - 'a']++; } // 因为 t 少遍历了一次，所以这里再进行处理 map[t.charAt(t.length() - 1) - 'a']++; // 遍历哈希表 for (int i = 0; i < 26; i++){ if (map[i] != 0){ return (char)('a' + i); } } return 'a'; }
解法三
思路
还是和 上面解法二的思路差不多，只不过，现在不用哈希表了，直接使用 int 进行加减，此消彼长，最后加减得到的数，就是 t 新增的字母
代码
/** * 执行用时分布 2 ms 击败 67.07% 消耗内存分布 42.34 MB 击败 79.87% * 使用 int 直接计数的方式，对字符串 s 出现的字母 和 字符串 t 出现的字母，相互抵消，最终得到的结果就是 t 新添加的子母 */ public char findTheDifference3(String s, String t) { int sum = 0; // 遍历 s 和 t for (int i = 0; i < s.length(); i++){ // sum = sum + t.charAt(i) + 'a' - (s.charAt(i) - 'a') // sum = sum + t.charAt(i) - s.charAt(i); sum += t.charAt(i) - s.charAt(i); } // 因为 t 少遍历了一次，所以这里再进行处理 sum += t.charAt(t.length() - 1) - 'a'; return (char)('a' + sum); }
