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

# 题目

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

示例：

s = "leetcode"
返回 0

s = "loveleetcode"
返回 2

提示：你可以假定该字符串只包含小写字母。

# 题解

思路是使用哈希表用来储存值，当遇到重复的值时，放到一个单独的哈希表里，然后再一次遍历即可找出不重复的。

TIP

执行用时：132 ms, 在所有 JavaScript 提交中击败了 52.11% 的用户
内存消耗：41.5 MB, 在所有 JavaScript 提交中击败了 22.31% 的用户

/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function(s) {
    if(s === '') return -1
    let hash = {} // 用来储存没有重复的值
    let repeatHash = {} // 用来储存重复的值

    for(let i=0;i<s.length;i++) {
        let item = s[i]
        // 如果值不为 undefined，说明是重复的值
        if(hash[item] != undefined) {
            // 把值存入 repeatHash 里面
            repeatHash[item] = i
        } else {
            hash[item] = i
        }
    }

    // 再一次遍历
    for(let i=0;i<s.length;i++) {
        let item = s[i]
        // 如果哈希表里面对应的值为 undefined，说明不是重复的值
        if(repeatHash[item] == undefined) {
            return i
        }
    }

    return -1
};

时间复杂度： `O(n)`，分别使用两个 for循环。使用 O(1) 的复杂度来判断元素是否存在
空间复杂度： `O(n)`，使用两个对象结构来储存值
最好情况：如果尽早的发现没有重复的值，那么会直接返回下标
最坏情况：在第二次循环后，没有发现重复的值，那么会完成整个循环

跟上面不同的是，使用每一个值作为哈希表的 key，出现次数作为值，所以第二次遍历时，如果值为 1，说明只出现一次。

TIP

执行用时：120 ms, 在所有 JavaScript 提交中击败了 76.42% 的用户
内存消耗：41.4 MB, 在所有 JavaScript 提交中击败了 23.17% 的用户

/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function(s) {
    if(s === '') return -1
    let hash = {}
    
    for(let i=0;i<s.length;i++) {
        let item = s.charAt(i)
        if(hash[item] == undefined) {
            hash[item] = 1
        } else {
            hash[item] += 1
        }
    }

    for(let i=0;i<s.length;i++) {
        let item = s.charAt(i)
        if(hash[item] === 1) {
            return i
        }
    }

    return -1
};

时间复杂度： `O(n)`，分别使用两个 for循环。使用 O(1) 的复杂度来判断元素是否存在`
空间复杂度： `O(n)`，使用一个对象结构来储存值
最好情况：如果尽早的发现没有重复的值，那么会直接返回下标
最坏情况：在第二次循环后，没有发现重复的值，那么会完成整个循环

首先外部进行一次遍历，然后内部在进行一次遍历，当遇到了相同的元素时，则跳出外部循环，否则说明找到没有重复的值，则直接返回即可。

TIP

执行用时：104 ms, 在所有 JavaScript 提交中击败了 95.78% 的用户
内存消耗：41 MB, 在所有 JavaScript 提交中击败了 29.89% 的用户

/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function(s) {
    if(s === '') return -1

    outer:
    for(let i=0;i<s.length;i++) {
        for(let j=0;j<s.length;j++) {
            if(s[j] == s[i] && j !== i) {
                continue  outer
            }
        }
        return i
    }

    return -1
};

时间复杂度： `O(n^2)`，使用了一个嵌套的 for循环，不过执行速度比上一个要快很多`
空间复杂度： `O(1)`，没有创建任何变量
最好情况：如果尽早的发现没有重复的值，那么会直接返回下标
最坏情况：全部为重复的情况，那么会重头遍历到结束

← 383 赎金信 389 找不同 →