题目描述

题目链接：387. First Unique Character in a String

Given a string, find the first non-repeating character in it and return its index. If it doesn’t exist, return -1.

例子

例子 1

Input: “leetcode”
Output: 0

例子 2

Input: “loveleetcode”
Output: 2

Note

You may assume the string contains only lowercase English letters.

解题思路

题目涉及统计字母出现个数，很自然想到一次遍历通过哈希表统计字母出现个数（这里由于题目指明字符串只包含小写字母，所以可以用 std::vector 作为哈希表），第二次遍历找出第一个出现次数为 1 的字符返回下标，否则返回 -1，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include <vector>
#include <string>

class Solution {
public:
    int firstUniqChar(std::string s) {
        std::vector<int> count(26, 0);
        for (char letter: s) {
            count[letter - 'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            if (count[s[i] - 'a'] == 1) return i;
        }
        return -1;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(1) 需要的哈希表空间是固定的所以可以理解为常数空间