桃园市网站建设_网站建设公司_搜索功能_seo优化

算法精解：如何高效找到字符串中第一个不重复的字符？

在处理字符串处理类算法题时，“频率统计”是一个核心思想。今天我们将通过LeetCode 387. 字符串中的第一个唯一字符这道经典题目，深入探讨两种主流解法：数组映射法与HashMap 计数法。

1. 题目描述

给定一个字符串s，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回-1。

示例：

• 输入:s = "leetcode"-> 输出:0
• 输入:s = "loveleetcode"-> 输出:2
• 输入:s = "aabb"-> 输出:-1

提示：

• s只包含小写字母。
• 字符串长度可达10510^5105。

2. 核心解题思路：两次遍历

无论是使用数组还是 HashMap，其核心逻辑都是相同的，即**“空间换时间”**。

1. 第一轮遍历：扫描整个字符串，统计每个字符出现的总次数。
2. 第二轮遍历：再次按索引顺序扫描字符串，检查当前字符在统计表中的次数是否为 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））
• 优点：
  1. 通用性强：如果题目要求处理的是中文字符、特殊符号或任意 Unicode 字符，数组法会因为范围太大失效，而HashMap可以轻松应对。
  2. 易读性：键值对语义明确，代码逻辑更符合直觉。

5. 两种解法对比分析

为什么数组通常更快？

在 Java 中，HashMap需要对基本类型进行装箱（int转Integer），并且在计算哈希槽、处理链表或红黑树结构时有额外的计算开销。而数组是连续的内存空间，CPU 缓存命中率更高。

6. 总结

• 如果面试题限制了小写字母，优先选择数组法，它的性能表现最完美。
• 如果面试题扩展到任意字符或需要更高的代码通用性，使用HashMap是更成熟的工程实践。

核心套路牢记：凡是涉及“第一个唯一”、“重复元素”、“频率统计”的问题，空间换时间（哈希思想）永远是你的首选策略！