算法精解：如何高效找到字符串中第一个不重复的字符？
在处理字符串处理类算法题时，“频率统计”是一个核心思想。今天我们将通过LeetCode 387. 字符串中的第一个唯一字符这道经典题目，深入探讨两种主流解法：数组映射法与HashMap 计数法。
1. 题目描述
给定一个字符串s，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回-1。
示例：
- 输入:
s = "leetcode"-> 输出:0 - 输入:
s = "loveleetcode"-> 输出:2 - 输入:
s = "aabb"-> 输出:-1
提示：
s只包含小写字母。- 字符串长度可达10510^5105。
2. 核心解题思路：两次遍历
无论是使用数组还是 HashMap，其核心逻辑都是相同的，即**“空间换时间”**。
- 第一轮遍历：扫描整个字符串，统计每个字符出现的总次数。
- 第二轮遍历：再次按索引顺序扫描字符串，检查当前字符在统计表中的次数是否为 1。第一个满足条件的索引即为答案。
3. 解法一：数组映射法（常规方法）
代码实现
classSolution{publicintfirstUniqChar(Strings){// 因为小写字母 ASCII 码或扩展 ASCII 范围内，256 足够覆盖int[]count=newint[256];// 1. 统计频率for(inti=0;i<s.length();i++){count[s.charAt(i)]++;}// 2. 查找第一个频率为 1 的字符索引for(inti=0;i<s.length();i++){if(1==count[s.charAt(i)])returni;}return-1;}}深度解析
- 原理：数组本质上是一个简单的哈希表。字符的 ASCII 值作为数组的下标（Index），数组存储的值（Value）则是出现的次数。
- 空间优化：题目提示只包含小写字母，其实可以使用
int[26]的数组，通过s.charAt(i) - 'a'将字符映射到 0-25 索引。使用int[256]更加通用，可以处理所有标准 ASCII 字符。 - 优点：访问数组的时间复杂度是O(1)O(1)O(1)，且没有哈希冲突和额外的对象开销，执行速度极快。
4. 解法二：HashMap 计数法
代码实现
classSolution{publicintfirstUniqChar(Strings){// 使用 HashMap 存储字符及其出现次数HashMap<Character,Integer>count=newHashMap<>();// 1. 统计频率for(inti=0;i<s.length();i++){charc=s.charAt(i);// 如果不存在则存入1，存在则在原值基础上+1count.put(c,count.getOrDefault(c,0)+1);}// 2. 查找第一个频率为 1 的字符索引for(inti=0;i<s.length();i++){if(count.get(s.charAt(i))==1)returni;}return-1;}}深度解析
- 原理：利用
HashMap的键值对（Key-Value）结构。Key 存储字符Character，Value 存储该字符出现的次数Integer。 - 代码逻辑：
count.getOrDefault(c, 0) + 1是一个优雅的写法，它代替了if(!containsKey)的条件判断，使代码更简洁。（虽然也可以使用HashMap的containsKey方法来检测是不是已经有了某个字符，但getOrDefault方法明显更加先进，直接内含了判断字符是否存在的逻辑，是就返回value(题中代码是返回的value＋1)，不存在就返回默认value(0)（题中代码在key不存在时，首次加入key的value也是0+1））
- 优点：
- 通用性强：如果题目要求处理的是中文字符、特殊符号或任意 Unicode 字符，数组法会因为范围太大失效，而
HashMap可以轻松应对。 - 易读性：键值对语义明确，代码逻辑更符合直觉。
- 通用性强：如果题目要求处理的是中文字符、特殊符号或任意 Unicode 字符，数组法会因为范围太大失效，而
5. 两种解法对比分析
| 维度 | 解法一：数组 (Array) | 解法二：HashMap |
|---|---|---|
| 时间复杂度 | O(N)O(N)O(N)- 遍历两次字符串 | O(N)O(N)O(N)- 遍历两次字符串 |
| 空间复杂度 | O(1)O(1)O(1)- 固定大小 (256 或 26) | O(1)O(1)O(1)或O(k)O(k)O(k)- 字符集大小 |
| 实际效率 | 极高（直接内存访问） | 一般（涉及对象开销、哈希计算） |
| 适用场景 | 字符范围固定（如仅字母/ASCII） | 字符范围未知或非常分散（如全 Unicode） |
为什么数组通常更快？
在 Java 中，HashMap需要对基本类型进行装箱（int转Integer），并且在计算哈希槽、处理链表或红黑树结构时有额外的计算开销。而数组是连续的内存空间，CPU 缓存命中率更高。
6. 总结
- 如果面试题限制了小写字母，优先选择数组法，它的性能表现最完美。
- 如果面试题扩展到任意字符或需要更高的代码通用性，使用HashMap是更成熟的工程实践。
核心套路牢记：凡是涉及“第一个唯一”、“重复元素”、“频率统计”的问题，空间换时间（哈希思想）永远是你的首选策略！
