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

链接：387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

思路

字符串只包含小写字母，也就是只有 26 种字符，那么就可以通过一个 26的 byte 数组来表示哪些是重复的，没出现过，未重复过的，在使用一个 List 来存储第一次出现字符的索引，如果字符前面已经出现过的，就不存进去，这个 list 数组最多也就是存进去26个索引

那么答案就只是从 List 中遍历，判断每个索引对应的字符是否重复过，如果都重复过，那么结果就是 -1，发现有一个是未重复的，那么结果就是这个索引

代码

/*** 387. 字符串中的第一个唯一字符* 执行用时分布 5 ms 击败 89.86% 消耗内存分布 44.38 MB 击败 49.25%* @param s 字符串* @return 字符串中的第一个唯一字符*/
public int firstUniqChar(String s) {// 用来表示 26 个字母中的重复情况// 0: 代表没有出现过，1：代表出现过，2：代表出现过多次byte[] chars = new byte[26];// 用于存储出现过一次的字符的下标List<Integer> list = new ArrayList<>();// 将字符串转换成字符数组，方便遍历char[] charArray = s.toCharArray();for (int i = 0; i < charArray.length; i++) {// 获取这个字符在 26个字符中的位置byte index = (byte)(charArray[i] - 'a');// 获取这个字符出现的次数byte num = chars[index];if (num == 0){// 将下标添加进 list 中list.add(i);chars[index] = 1;} else if (num == 1){// 代表出现多次chars[index] = 2;}}// 遍历 list，过滤出后面出现重复的字符for (Integer i : list) {// 获取这个字符在 26个字符中的位置byte index = (byte)(charArray[i] - 'a');// 获取这个字符出现的次数byte num = chars[index];if (num == 1){return i;}}return -1;
}

优化

我尝试了几次都没法将运行时间缩减至 4ms，最后将 list 替换成普通的 int 数组，ArrayList 底层如果空间不足会进行扩容，换成普通的 int 数组，缩减掉了这些过程

public int firstUniqChar(String s) {// 用来表示 26 个字母中的重复情况// 0: 代表没有出现过，1：代表出现过，2：代表出现过多次byte[] chars = new byte[26];// 用于存储出现过一次的字符的下标int[] first = new int[26];int firstIndex = 0;// 将字符串转换成字符数组，方便遍历char[] charArray = s.toCharArray();for (int i = 0; i < charArray.length; i++) {// 获取这个字符在 26个字符中的位置byte index = (byte)(charArray[i] - 'a');// 获取这个字符出现的次数byte num = chars[index];if (num == 0){// 将下标添加进 list 中first[firstIndex++] = i;chars[index] = 1;} else if (num == 1){// 代表出现多次chars[index] = 2;}}// 遍历 first，过滤出后面出现重复的字符for (Integer i : first) {// 获取这个字符在 26个字符中的位置byte index = (byte)(charArray[i] - 'a');// 获取这个字符出现的次数byte num = chars[index];if (num == 1){return i;}}return -1;
}