https://leetcode.cn/problems/find-the-difference/description/

简单来说 t 是由 s 随机重排，并添加一个字母而来的，那么已知：

通过使用 哈希表，通过对两个字符串的字符索引（规则：字母 - '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);
}

链接：https://leetcode.cn/problems/find-the-difference/description/

389. 找不同

算法

编程语言

开发工具

LeetCode题目"Find the Difference"的三种解法详解：通过哈希表计数、抵消法和整数加减法，找出字符串t中新增的字母。文章提供完整Java代码，时间复杂度O(n)，空间复杂度O(1)，包含性能优化技巧和字符索引计算原理，适合算法学习者参考。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

EdgeOne AI 安全实战专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

389. 找不同

389. 找不同

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐