题目的主要信息：

• 在给定字符串中找到第一个只出现一次的字符的位置，从0开始
• 如果找不到则返回-1
• 字符串只有大小字母组成
• 要求：空间复杂度$O(n)O(n)$，时间复杂度$O(n)O(n)$

方法一：哈希表统计频率

具体做法：

我们可以建立一个无序哈希表，遍历字符串的同时，统计每个字符出现的频率，然后再从头遍历一次字符串，在哈希表中查看每个字符串的频率，找到第一个只出现一次的字符串，返回位置，如果没找到返回-1即可。

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        unordered_map<char, int> mp;
        for(int i = 0; i < str.length(); i++) //统计每个字符出现的次数
            mp[str[i]]++;
        for(int i = 0; i < str.length(); i++) //找到第一个只出现一次的字母
            if(mp[str[i]] == 1)
                return i;
        return -1; //没有找到
    } 
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，两次单独的遍历
• 空间复杂度：$O(1)O(1)$，哈希表的大小最多不会超过字符集，即52个字符，属于常数空间

方法二：队列+哈希表统计位置

具体做法：

我们还可以只遍历一次，利用队列找到第一个位置。首先我们还是利用了无序哈希表，但是这次我们不是统计频率，而是统计每个字符出现位置。遍历字符串，如果遇到哈希表中没有的字符，我们入哈希表，同将字符和位置组成pair入队，然后后续如果遇到了哈希表中出现的字符，那么这个字符势必不可能是我们要找的只出现一次的字符，在哈希表中将其位置置为-1，然后弹出队列中在前面的哈希表中位置为-1的字符。因为队列是先进先出，因此队列头记录的字符一定是第一次只出现一次的字符。空队列则代表没有找到。

class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        unordered_map<char, int> mp; //统计字符出现的位置
        queue<pair<char, int> > q; 
        for(int i = 0; i < str.length(); i++){
            if(!mp.count(str[i])){ //没有出现过的字符
                mp[str[i]] = i; 
                q.push(make_pair(str[i], i));
            }else{ //找到重复的字符
                mp[str[i]] = -1; //位置置为-1
                while(!q.empty() && mp[q.front().first] == -1) //弹出前面所有的重复过的字符
                    q.pop();
            }
        }
        return q.empty() ? -1 : q.front().second;
    } 
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，对字符串进行一次遍历，内循环整个过程中才最多弹出52次
• 空间复杂度：$O(1)O(1)$，哈希表和队列的大小最多不会超过字符集，即52个字符，属于常数空间