387. 字符串中的第一个唯一字符 - Leetcode

解题思路

遍历字符串 s ，使用哈希表统计 “各字符数量是否 $> 1$ ”。
再遍历字符串 s ，在哈希表中找到首个 “数量为 $1$ 的字符”，并返回。

{:width=450}

算法流程：

初始化： 字典 (Python)、HashMap(Java)、map(C++)，记为 dic 。
字符统计： 遍历字符串 s 中的每个字符 c 。
1. 若 dic 中 不包含 键(key) c ：则向 dic 中添加键值对 (c, True) ，代表字符 c 的数量为 $1$ 。
2. 若 dic 中包含键(key) c ：则修改键 c 的键值对为 (c, False) ，代表字符 c 的数量 $> 1$ 。
查找数量为 $1$ 的字符： 遍历字符串 s 中的每个字符 c 。
1. 若 dic中键 c 对应的值为 True ：，则返回其索引。
2. 否则，返回 -1 ，代表不存在数量为 $1$ 的字符。

<,,,,,,,,,,>

代码：

Python 代码中的 not c in dic 整体为一个布尔值； c in dic 为判断字典中是否含有键 c 。

Python

class Solution:
    def firstUniqChar(self, s: str) -> int:
        dic = {}
        for c in s:
            dic[c] = not c in dic
        for i, c in enumerate(s):
            if dic[c]: return i
        return -1

Java

class Solution {
    public int firstUniqChar(String s) {
        HashMap<Character, Boolean> dic = new HashMap<>();
        char[] sc = s.toCharArray();
        for(char c : sc)
            dic.put(c, !dic.containsKey(c));
        for(int i = 0; i < sc.length; i++)
            if(dic.get(sc[i])) return i;
        return -1;
    }
}

C++

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, bool> dic;
        for(char c : s)
            dic[c] = dic.find(c) == dic.end();
        for(int i = 0; i < s.size(); i++)
            if(dic[s[i]]) return i;
        return -1;
    }
};

复杂度分析：

时间复杂度 $O(N)$ ： $N$ 为字符串 s 的长度；需遍历 s 两轮，使用 $O(N)$ ；HashMap 查找操作的复杂度为 $O(1)$ 。
空间复杂度 $O(1)$ ： 由于题目指出 s 只包含小写字母，因此最多有 26 个不同字符，HashMap 存储需占用 $O(26) = O(1)$ 的额外空间。