LeetCode题练习与总结：字符串中的第一个唯一字符--387

一、题目描述

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

示例 1：

输入: s = "leetcode"
输出: 0

示例 2:

输入: s = "loveleetcode"
输出: 2

示例 3:

输入: s = "aabb"
输出: -1

提示:

• 1 <= s.length <= 10^5
• s 只包含小写字母

二、解题思路

1. 创建一个长度为26的整型数组，用于记录每个字符出现的次数。数组的索引对应字符 ‘a’ 到 ‘z’。
2. 遍历字符串，对于每个字符，将其在数组中的对应位置加1。
3. 再次遍历字符串，对于每个字符，检查其在数组中的对应位置的值是否为1，如果是，则返回当前字符的索引。
4. 如果遍历完字符串后，没有找到只出现一次的字符，返回-1。

三、具体代码

class Solution {public int firstUniqChar(String s) {// 创建一个长度为26的数组，初始化为0int[] charCount = new int[26];// 遍历字符串，记录每个字符出现的次数for (int i = 0; i < s.length(); i++) {charCount[s.charAt(i) - 'a']++;}// 再次遍历字符串，找到第一个出现一次的字符for (int i = 0; i < s.length(); i++) {if (charCount[s.charAt(i) - 'a'] == 1) {return i; // 返回该字符的索引}}// 如果没有找到，返回-1return -1;}
}

这段代码首先通过两个循环来记录和检查字符的出现次数，第一个循环用于统计每个字符出现的次数，第二个循环用于找到第一个只出现一次的字符。如果找到了，就返回它的索引；如果遍历结束后都没有找到，则返回-1。

四、时间复杂度和空间复杂度

1. 时间复杂度

• 第一个循环用于遍历字符串 s，其长度为 n（字符串的长度）。在这个循环中，我们执行了 n 次操作（每次操作都是常数时间复杂度，即 O(1)），因此第一个循环的时间复杂度是 O(n)。

• 第二个循环也是遍历字符串 s，同样执行了 n 次操作。因此，第二个循环的时间复杂度也是 O(n)。

• 两个循环是顺序执行的，所以总的时间复杂度是两个循环的时间复杂度之和，即 O(n) + O(n) = O(n)。

2. 空间复杂度

• 我们创建了一个固定大小的整型数组 charCount，其大小为 26，这是因为英文字母表中有26个小写字母。这个数组的大小与输入字符串的长度无关，因此空间复杂度是 O(1)。

五、总结知识点

1. 类定义：定义了一个名为 Solution 的公共类。

2. 方法定义：在类中定义了一个公共方法 firstUniqChar，该方法接受一个字符串参数 s 并返回一个整数。

3. 数组初始化：使用 new int[26] 创建了一个整型数组 charCount，长度为26，用于存储每个小写字母出现的次数。

4. 字符与整数的转换：使用 s.charAt(i) - 'a' 将字符转换为对应的整数索引。这是因为字符 ‘a’ 到 ‘z’ 在 ASCII 表中是连续的，所以减去 ‘a’ 的 ASCII 值可以得到一个从 0 到 25 的索引。

5. 数组操作：通过 charCount[s.charAt(i) - 'a']++ 来增加数组中对应字符的计数。

6. 循环结构：使用了两个 for 循环，第一个循环用于遍历字符串并统计字符出现次数，第二个循环用于找到第一个只出现一次的字符。

7. 条件判断：使用 if 语句检查数组中特定索引的值是否等于1，以确定该字符是否只出现一次。

8. 方法返回值：使用 return 语句返回找到的第一个不重复字符的索引，或者如果没有找到则返回 -1。

9. 字符串长度：使用 s.length() 获取字符串的长度。

10. 常量：在代码中使用了常量 -1 作为找不到不重复字符时的返回值。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。