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

难度：简单
题目描述：

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

案例:

s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

注意事项：您可以假定该字符串只包含小写字母。

思路：
设置字典表，循环两次，第一次把每个字符的索引存储到字典表中，第二次遍历，只要该位置的字符在字典表中没有和现有的位置不对应，即该字符出现了不止一次，

ps：也可以用该方法统计一个字符串中每一个字符出现的次数。
时间复杂度O(n)，空间复杂度O(1)

代码如下：

public int firstUniqChar(String s) {
    int[] arr = new int[128];
    for(int i = 0; i < s.length();i++) {
        arr[s.charAt(i)] = i + 1;
    }
    for(int i = 0; i < s.length(); i++) {
        if(arr[s.charAt(i)] == i + 1) return i;
        else arr[s.charAt(i)] = 0;
    }
    return -1;
}

运行提交之后，执行用时 :19 ms, 在所有 Java 提交中击败了75.55%的用户，
学习最优的代码，

public int firstUniqChar(String s) {
    int index = -1;
    for (char i='a';i<='z';i++){
        int startindex = s.indexOf(i);
        if (startindex != -1 && startindex == s.lastIndexOf(i)){
            index = (index == -1 || index > startindex) ? startindex : index;
        }
    }
    return index;
}

该方法只循环26次，每次循环找出该字符在字符串出现的第一个位置和最后一个位置是否相等，找出最小的那个字符的位置，返回。时间复杂度最优O(1),最差O(n)

学习该方法的时候，想起来另一种做法,对字符串循环遍历，从第一个开始，每次找出第一个和最后一个，如何位置相等，直接返回。
代码如下：

public int firstUniqChar(String s) {
    int index = -1;
    char ch;
    int len = s.length();
    int[] arr = new int[26];
    for (int i = 0; i < len; i++) {
        ch = s.charAt(i);
        if (arr['z' - ch] == 1) continue;
        int j = len - 1;
        for (; j >= 0; j--) {
            if (ch == s.charAt(j)) break;
        }
        if (i == j) return i;
        else arr['z' - ch] = 1;
    }
    return index;
}

速度比刚刚快了3ms，但是，该方法的时间复杂度也不稳定，最优时间复杂度O(1)，最差O(N^2)。不可取。

总结：解题的方法有很多种，但是对应的时间复杂度和空间复杂度各不相同，具体应用，还得看具体的场景，如果处理很长的字符串可以采用，第二种循环字符的方式，对于不太长的字符串可以使用字典表的方法。每天进步一点点，加油O(∩_∩)O