難度：簡(jiǎn)單
題目描述：

給定一個(gè)字符串，找到它的第一個(gè)不重復(fù)的字符，并返回它的索引。如果不存在，則返回 -1。

案例:

s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

注意事項(xiàng)：您可以假定該字符串只包含小寫字母。

思路：
設(shè)置字典表，循環(huán)兩次，第一次把每個(gè)字符的索引存儲(chǔ)到字典表中，第二次遍歷，只要該位置的字符在字典表中沒(méi)有和現(xiàn)有的位置不對(duì)應(yīng)，即該字符出現(xiàn)了不止一次，

ps：也可以用該方法統(tǒng)計(jì)一個(gè)字符串中每一個(gè)字符出現(xiàn)的次數(shù)。
時(shí)間復(fù)雜度O(n)，空間復(fù)雜度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;
}

運(yùn)行提交之后，執(zhí)行用時(shí) :19 ms, 在所有 Java 提交中擊敗了75.55%的用戶，
學(xué)習(xí)最優(yōu)的代碼，

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;
}

該方法只循環(huán)26次，每次循環(huán)找出該字符在字符串出現(xiàn)的第一個(gè)位置和最后一個(gè)位置是否相等，找出最小的那個(gè)字符的位置，返回。時(shí)間復(fù)雜度最優(yōu)O(1),最差O(n)

學(xué)習(xí)該方法的時(shí)候，想起來(lái)另一種做法,對(duì)字符串循環(huán)遍歷，從第一個(gè)開始，每次找出第一個(gè)和最后一個(gè)，如何位置相等，直接返回。
代碼如下：

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，但是，該方法的時(shí)間復(fù)雜度也不穩(wěn)定，最優(yōu)時(shí)間復(fù)雜度O(1)，最差O(N^2)。不可取。

總結(jié)：解題的方法有很多種，但是對(duì)應(yīng)的時(shí)間復(fù)雜度和空間復(fù)雜度各不相同，具體應(yīng)用，還得看具體的場(chǎng)景，如果處理很長(zhǎng)的字符串可以采用，第二種循環(huán)字符的方式，對(duì)于不太長(zhǎng)的字符串可以使用字典表的方法。每天進(jìn)步一點(diǎn)點(diǎn)，加油O(∩_∩)O