字符串中的第一个唯一字符（387）

题目

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

示例

s = "leetcode" 返回 0

s = "loveleetcode" 返回 2

提示

你可以假定该字符串只包含小写字母

算法

哈希表 + 遍历

按照{字符：出现次数}保存map，然后遍历字符串找到第一个值为1的键

export const firstUniqChar = (s) => {
	const map = new Map();
	for (const character of s) {
		if (map.has(character)) {
			map.set(character, map.get(character) + 1);
		} else {
			map.set(character, 1);
		}
	}
	for (let i = 0; i < s.length; i++) {
		if (map.get(s[i]) === 1) {
			return i;
		}
	}
	return -1;
};

数组 + 遍历

因为都是小写字母，创建一个长度为26的数组，按照字符ascii码-97===数组下标的规则维护数组

遍历字符串，对应上面创建的字幕出现次数的数组，找到第一个值为1的字母

export const firstUniqChar = (s) => {
	let charArr = new Array(26).fill(0);
	for (const character of s) {
		charArr[character.charCodeAt() - 97]++;
	}
	for (let i = 0; i < s.length; i++) {
		if (charArr[s[i].charCodeAt() - 97] === 1) {
			return i;
		}
	}
	return -1;
};

内置方法

出现一次：从前查找索引===从后查找索引

export const firstUniqChar = (s) => {
	for (let i = 0; i < s.length; i++) {
		if (s.indexOf(s[i]) === s.lastIndexOf(s[i])) {
			return i;
		}
	}
	return -1;
};

hashMap + 队列

使用Map来保存字母和其最后出现位置

使用队列queue来保存没有重复出现的字母且保持相对位置，如果队列头有重复出现的字母我们就推出，最后队列头部就是第一个没有重复的字母，如果队列为空则字符串中没有只出现一次的字母

我们遍历字符串：

• 如果字母在Map中没有出现过，那我们在Map中保存它出现的位置（所以这个值大于等于0），并且以[ch, index]的形式推入队列queue
• 如果字母在Map中出现，那么说明这个字母重复了，我们在Map中将其值改为-1（表示重复出现），然后我们检查队列头，如果队列queue不为空而且队列头部的元素在Map中标记了位置为-1（即这个元素重复出现过）,那么我们将这个元素推出队列

最后我们检查队列是否为空，如果不为空那么队列头部的元素一定是第一个不重复的字母，我们返回他的位置queue[0][1]

export const firstUniqChar = (s) => {
	const queue = [];
	const map = new Map();
	Array.prototype.forEach.call(s, (ch, i) => {
		if (map.has(ch)) {
			if (map.get(ch)[1] !== -1) map.set(ch, -1);
			while (queue.length && map.get(queue[0][0]) === -1) queue.shift();
		} else {
			queue.push([ch, i]);
			map.set(ch, i);
		}
	});
	return queue.length ? queue[0][1] : -1;
};