如何用哈希表找到第一个不重复字符？

简化版

第一个不重复字符可以先用哈希表或固定数组统计每个字符出现次数，再从左到右扫原字符串，找到第一个次数为 1 的字符。统计 O(n)，二次扫描 O(n)，整体 O(n)。

详细版

这题不是只找“有没有不重复”，还要求“第一个”，所以统计完次数后必须回到原字符串按顺序查。若字符集是小写英文字母，用长度 26 的数组；字符集不固定，用 HashMap。

int firstUniqChar(String s) {
    int[] count = new int[26];
    for (char c : s.toCharArray()) count[c - 'a']++;
    for (int i = 0; i < s.length(); i++) {
        if (count[s.charAt(i) - 'a'] == 1) return i;
    }
    return -1;
}

如果是 Unicode 字符，不能简单用 26 位数组，要换成 Map 或按码点处理。

完整版教学

一、为什么需要两遍扫描

第一遍解决“每个字符出现几次”，第二遍解决“谁最靠前”。如果只统计次数，不回原字符串，就丢了顺序；如果只从左到右找，遇到某字符时还不知道后面会不会重复。

例如 leetcode 中，第一遍统计后 l 的次数是 1，第二遍从下标 0 看到 l 就返回。

二、哈希表和数组怎么选

如果题目限定小写英文字母，字符空间只有 26 个，用数组更快更省。若字符集可能是 ASCII、Unicode、中文或大小写混合，就用 HashMap 更通用。

字符集	推荐结构	原因
小写 a-z	`int[26]`	空间固定、访问快
ASCII	`int[128]` 或 `int[256]`	简单直接
不确定字符	`Map<Character,Integer>`	通用

面试时要先读清楚输入约束，不要默认只有小写字母。

三、为什么不能用 Set 一次解决

Set 只能表示出现过，无法区分出现 1 次还是多次。可以用两个 Set：一个记录出现过，一个记录重复过，但最后仍要按原字符串顺序找第一个不在重复集合里的字符。计数表更直观。

seen: 出现过
duplicated: 出现超过一次
第一个不重复 = 从左到右找不在 duplicated 中的字符

本质仍然是哈希记录频次或状态。

四、按顺序返回为什么重要

“第一个”指原字符串中的最小下标，不是字典序最小，也不是哈希表遍历出来的第一个。HashMap 普通遍历不保证顺序，不能直接遍历 map 找 count=1。

例如 loveleetcode 中，v 和 l 都可能出现一次，但答案是下标 2 的 v，必须以原串顺序为准。

五、复杂度和工程边界

两遍扫描都是 O(n)，计数数组空间 O(1) 因为字符集固定；HashMap 空间 O(m)，m 是不同字符数量。若处理 Unicode，Java 的 char 是 UTF-16 代码单元，某些 emoji 需要按 code point 处理，不能简单按 char 等价字符。

算法题通常限定小写字母，此时 26 数组就是最优解。

六、常见误区与追问

记忆钩子：计数表回答“重复不重复”，原字符串顺序回答“第一个是谁”。

误区：遍历 HashMap 找第一个 count=1。 HashMap 不保证原字符串顺序，会返回错误位置。
误区：Set 可以直接判断唯一。 Set 只能表示存在，不能表达出现次数。
误区：默认所有输入都是小写字母。 字符集不确定时要改 Map 或更大数组。
追问：能一遍做吗？ 可以用有序队列维护候选，但实现复杂；两遍计数更稳。
追问：空间能否 O(1)？ 固定字符集下可以，因为数组大小固定。
追问：如果要返回字符而不是下标？ 找到下标后返回 s.charAt(i) 即可；没有则返回约定值。

七、加强记忆

第一个不重复字符是“计数 + 顺序”的组合题。第一遍用哈希或数组记录频次，第二遍按原字符串查第一个频次为 1 的位置。凡是题目带“第一个/最左边”，都要警惕哈希表自身无序，答案顺序要回到原数据中确认。

简化版

详细版