题目描述

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

案例:

s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

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

标签 哈希表 字符串

https://leetcode-cn.com/problems/first-unique-character-in-a-string/

解题思路

这道题最优的解法就是线性复杂度了，为了保证每个元素是唯一的，至少得把每个字符都遍历一遍。

算法的思路就是遍历一遍字符串，然后把字符串中每个字符出现的次数保存在一个散列表中。这个过程的时间复杂度为 O(N)，其中 N 为字符串的长度。

接下来需要再遍历一次字符串，这一次利用散列表来检查遍历的每个字符是不是唯一的。如果当前字符唯一，直接返回当前下标就可以了。第二次遍历的时间复杂度也是 O(N)。

正常哈希表写法，但因为语言实现的原因，速度比较慢。

/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function(s) {
    let hash = new Map()
    
    for(let i = 0; i < s.length; i++) {
        if(hash.has(s[i])) {
            hash.set(s[i], hash.get(s[i]) + 1)
        } else {
            hash.set(s[i], 1)
        }
    }
    
    for(let i = 0; i < s.length; i++) {
        if(hash.get(s[i]) == 1){
            return i
        }
    }
    return -1
};

语言自带字符串api实现。indexOf从左找出现第一个，lastIndexOf从右找出现第一个。

如果两个下标一样，那说明这个值就是唯一字符。

字符串是从左到右遍历的，所以只要indexOf和lastIndexOf的下标一样，那说明这个值就是字符串中的第一个唯一字符

/**
 * @param {string} s
 * @return {number}
 */
var firstUniqChar = function(s) {
  let temp
  for (let i = 0; i < s.length; i++) {
    temp = s[i]
    if (s.indexOf(temp) === i && s.lastIndexOf(temp) === i) {
      return i
    }
  }
  return -1
};