Easy

题目描述

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

示例 1:

输入: s = "leetcode"
输出: 0
解释: 字符 'l' 在索引 0 处是第一个不在其他任何索引处出现的字符。

示例 2:

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

示例 3:

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

提示:

  • 1 <= s.length <= 10^5
  • s 只由小写英文字母组成。

解题思路

解题思路

这道题要求找到字符串中第一个不重复的字符索引，典型的字符频次统计问题。

方法一：两次遍历（推荐）

  1. 第一次遍历：统计每个字符出现的频次，可以使用哈希表或数组
  2. 第二次遍历：按原始顺序遍历字符串，找到第一个频次为1的字符

由于题目限定只有小写英文字母，可以用大小为26的数组替代哈希表，提高效率。

方法二：一次遍历 + 队列

使用队列维护可能的候选字符，同时用哈希表记录频次。当发现字符重复时，从队列头部移除已重复的字符。

方法三：内置函数

对于每个字符，检查它第一次和最后一次出现的位置是否相同。

两次遍历法是最直观且高效的解法，时间复杂度O(n)，空间复杂度O(1)（使用固定大小数组）。

代码实现

class Solution {
public:
    int firstUniqChar(string s) {
        vector<int> count(26, 0);
        
        // 第一次遍历：统计每个字符的频次
        for (char c : s) {
            count[c - 'a']++;
        }
        
        // 第二次遍历：找到第一个频次为1的字符
        for (int i = 0; i < s.length(); i++) {
            if (count[s[i] - 'a'] == 1) {
                return i;
            }
        }
        
        return -1;
    }
};

class Solution:
    def firstUniqChar(self, s: str) -> int:
        # 第一次遍历：统计每个字符的频次
        count = {}
        for c in s:
            count[c] = count.get(c, 0) + 1
        
        # 第二次遍历：找到第一个频次为1的字符
        for i, c in enumerate(s):
            if count[c] == 1:
                return i
        
        return -1

public class Solution {
    public int FirstUniqChar(string s) {
        int[] count = new int[26];
        
        // 第一次遍历：统计每个字符的频次
        foreach (char c in s) {
            count[c - 'a']++;
        }
        
        // 第二次遍历：找到第一个频次为1的字符
        for (int i = 0; i < s.Length; i++) {
            if (count[s[i] - 'a'] == 1) {
                return i;
            }
        }
        
        return -1;
    }
}

var firstUniqChar = function(s) {
    const charCount = {};
    
    for (let char of s) {
        charCount[char] = (charCount[char] || 0) + 1;
    }
    
    for (let i = 0; i < s.length; i++) {
        if (charCount[s[i]] === 1) {
            return i;
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度数值说明
时间复杂度O(n)需要遍历字符串两次，每次O(n)
空间复杂度O(1)使用固定大小的数组（26个字母）或哈希表

相关题目