【OJ题解】在字符串中查找第一个不重复字符的索引

💵个人主页: 起名字真南
💵个人专栏:【数据结构初阶】 【C语言】 【C++】 【OJ题解】

1. 引言

在字符串处理相关问题中，查找第一个不重复字符的索引是一个经典题目。特别是在高并发环境中，我们可能需要高效判断某个字符串的字符是否有重复。本文将详细解析如何在给定字符串中找到第一个不重复字符的索引。

2. 题目分析

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

在字符串中查找第一个不重复字符的索引题目链接

示例：

• 示例 1：
  • 输入：s = "leetcode"
  • 输出：0（因为第一个不重复字符是 l，索引为 0）
• 示例 2：
  • 输入：s = "loveleetcode"
  • 输出：2（第一个不重复字符是 v，索引为 2）
• 示例 3：
  • 输入：s = "aabb"
  • 输出：-1（所有字符都重复）

3. 解题思路

这道题可以通过双重循环和哈希表两种思路来实现。双重循环简单直接，但在处理大型字符串时效率较低。本文将以双重循环方法为主，之后讨论优化方法。

思路一：双重循环

我们逐个检查字符串中的每个字符，并在整个字符串中寻找其他相同字符。若发现相同字符，则跳过；否则，返回该字符的索引。

思路二：哈希表

可以用哈希表记录每个字符出现的次数。之后再遍历字符串，查找第一个只出现一次的字符。

4. C++代码实现

以下为C++代码，使用双重循环来实现第一个不重复字符的查找：

class Solution {
public:int firstUniqChar(string s) {int len = s.size();// 遍历字符串中的每个字符for (int i = 0; i < len; i++) {bool isUnique = true; // 假设当前字符是唯一的for (int j = 0; j < len; j++) {// 检查是否有其他相同字符if (s[i] == s[j] && i != j) {isUnique = false;break;}}// 如果是唯一字符，返回其索引if (isUnique) {return i;}}return -1; // 没有找到不重复字符}
};

5. 代码详解

• 外层循环：遍历字符串中的每一个字符 s[i]，并假设该字符是唯一的。
• 内层循环：检查 s[i] 是否在其他位置出现：
  • 如果找到与 s[i] 相同的字符，则将 isUnique 标记为 false，并跳出内层循环。
• 返回索引：如果 isUnique 仍然为true，表示当前字符是唯一的，返回它的索引i。
• 返回-1：如果遍历结束没有找到不重复字符，返回 -1。

6. 时间和空间复杂度分析

• 时间复杂度：O(n^2)，其中 n 是字符串的长度。外层循环遍历字符串中的每个字符，内层循环遍历整个字符串来寻找重复字符，因此时间复杂度为 O(n^2)。
• 空间复杂度：O(1)，仅使用了常数级额外空间。

7. 优化方法

尽管双重循环方法简单易懂，但在长字符串中效率较低。可以使用哈希表优化到线性时间复杂度。

使用哈希表优化的思路：

1. 首次遍历字符串，将每个字符的出现次数记录到哈希表中。
2. 再次遍历字符串，找到第一个只出现一次的字符并返回其索引。

优化后的代码如下：

#include <unordered_map>class Solution {
public:int firstUniqChar(string s) {unordered_map<char, int> countMap;// 统计每个字符出现的次数for (char c : s) {countMap[c]++;}// 再次遍历字符串，找到第一个只出现一次的字符for (int i = 0; i < s.size(); i++) {if (countMap[s[i]] == 1) {return i;}}return -1;}
};

8. 时间和空间复杂度分析（哈希表实现）

• 时间复杂度：O(n)，因为哈希表方法只需要两次遍历字符串。
• 空间复杂度：O(1)，因为哈希表中的键值对不会超过字符数量。

9. 总结

本文介绍了如何查找字符串中第一个不重复字符的索引。虽然双重循环方法能有效解决问题，但在大型数据下不够高效。哈希表优化方法可以大幅提升效率，适用于各种字符串长度。希望通过此文章能帮助大家更好地理解字符串不重复字符查找的实现。

今后可以探索更多优化方法，如基于字符ASCII码的统计数组，以实现更快的查找操作。