389. 找不同

链接：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);
}