字符串中的第一个唯一字符解析

题目

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

示例：


s = "leetcode"
返回 0

s = "loveleetcode"
返回 2

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

解法1


var firstUniqChar = function (s) {
	const h = new Map();

  for (let i = 0; i < s.length; i++) {
    if (h.has(s[i])) {
      h.set(s[i], h.get(s[i]) + 1);
    } else {
      h.set(s[i], 1);
    }
  }

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

  return -1;
};

这种解法先用hash将每个字母出现的顺序先通过一次遍历计算出来，然后利用第二次遍历，查看每一个字母出现的次数是否为0，如果为0则返回

解法2


var firstUniqChar = function (s) {
  const arr = new Array(26);

  const charCodeAtA = "a".charCodeAt();

  const charIndex = (i) => s[i].charCodeAt() - charCodeAtA;
  for (let i = 0; i < s.length; i++) {
    arr[charIndex(i)] = i;    
  }

  for (let i = 0; i < s.length; i++) {
    if (arr[charIndex(i)] === i){
      return i;
    }else{
      arr[charIndex(i)] = -1
    }
  }

  return -1
};

解法二同样是通过两次遍历，但是是用数组来保存字母最后一次出现的位置，然后注意在第二次遍历时比较的时，第一次遇到当前下标和记录下标相同时说明确实是第一次出现，否则把记录下标设为-1，保证以后不会匹配

解法3

将上面的记录最后一次出现的位置改为记录出现次数，第二次循环匹配出现次数为1的，这种写法综合两种优劣，简单易懂。

hash是否就是最好的

在第一种解法中看似hash是用来查找次数的好方法，但是实践中却没有解法二或者三快，因为确定大小的数组下标索引依然还是比hash查找要快，所以看到这种题不要一直想着用hash解决，观察被查找组的数据量，看是否能用有限量的数组去解决