leetcode387： 字符串中第一个唯一字符

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

使用hash表存储频数。对字符串进行2次遍历。

第一次遍历统计频数。第二次遍历找到频数为1的字符下标。

int index = -1;
HashMap map = new HashMap<>();
for(int i = 0; i < s.length();i++){
    if(map.containsKey(s.charAt(i))){
        map.put(s.charAt(i),map.get(s.charAt(i))+1);
    }else{
        map.put(s.charAt(i),1);
    }
}
​
for(int i = 0 ; i < s.length();i++){
    if(map.get(s.charAt(i)) == 1){
        index = i;
        break;
    }
}
return index;
​
解答成功:
            执行耗时:34 ms,击败了10.53% 的Java用户
            内存消耗:38.9 MB,击败了60.55% 的Java用户

使用哈希表存储元素和它的下标。当元素出现多次（两次及两次以上）时，将下标改为-1。

然后将哈希表遍历一遍找到最小的下标。

public int firstUniqChar(String s) {
    
​
    int index = s.length();
    HashMap map = new HashMap<>();
    for(int i = 0; i < s.length();i++){
        if(map.containsKey(s.charAt(i))){
            map.put(s.charAt(i),-1);
        }else{
            map.put(s.charAt(i),i);
        }
    }
    for (Integer value : map.values()) {
        if(value!=-1 && value < index){
            index = value;
        }
    }
    if(index == s.length()){
        index = -1;
    }
    return index;
}
    执行耗时:27 ms,击败了29.50% 的Java用户
            内存消耗:38.9 MB,击败了66.15% 的Java用户

由于只有小写字符，总共26个，可以使用数组替换哈希表实现。

相比于思路1，性能提高很大。

public int firstUniqChar(String s) {
    int[] index = new int[26];
    for(int i = 0; i < s.length();i++){
        index[s.charAt(i)-'a']++;
    }
​
    for(int i = 0 ; i < s.length();i++){
        if(index[s.charAt(i)-'a']==1){
            return i;
        }
    }
    return -1;
}
​
执行耗时:7 ms,击败了70.00% 的Java用户
            内存消耗:38.9 MB,击败了58.50% 的Java用户

因此可以考虑遍历26个字母，对于每一个字母，先使用indexof方法找到首次出现的下标，再使用lastindexof方法找到最后出现的下标，如果这2个值相等，则说明它出现了一次。

大大减少了循环的时间复杂度。

public int firstUniqChar(String s) {
    int min = s.length();
    for(int i = 0 ; i < 26;i++){
        int first = s.indexOf('a'+i);
        int end = s.lastIndexOf('a'+i);
        if(first != -1 && first == end && first < min){
            min = first;
        }
    }
​
    if(min == s.length()){
        min = -1;
    }
    return min;
}
​
解答成功:
            执行耗时:2 ms,击败了99.19% 的Java用户
            内存消耗:39 MB,击败了41.62% 的Java用户

参考：leetcode