:-: 6.7 字符串中的第一个唯一字符 ***** **题干：** 给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。 案例: ``` s = "leetcode" 返回 0. s = "loveleetcode", 返回 2. ``` 注意事项：您可以假定该字符串只包含小写字母。 **题目分析：** 我们要找出字符串第一个没有重复的字符，返回该字符的位置，我们假定该字符串只包含小写字母，也就是说我们找的字符就在这小写的26个字母当中，题目给的条件绝不是没有目的的。 **新手有可能遇到的解题思路陷阱：** 没有处理空字符串、以及只有一个字符的字符串，或者双重循环忽略本身和本身会相等的情况。 **解题思路分析以及代码实现：** 第一种思路：双重嵌套循环对比法。 第一种思路代码： ``` public int firstUniqChar(String s) { if (s == null || "".equals(s) || s.isEmpty()) { return -1; } char[] ss = s.toCharArray(); if (ss.length == 1) { return 0; } for (int i = 0; i < ss.length; i++) { boolean sign = true; for (int j = 0; j < ss.length; j++) { if (i != j && ss[i] == ss[j]) { sign = false; break; } } if (sign) { return i; } } return -1; } ``` **复杂度分析** 时间复杂度：O(n^2)。 空间复杂度：O(n)。 第二种思路：双循环字母表法。此方式如果字符串特别长且目标字符又在末端则十分缓慢。 第二种思路代码： ``` public int firstUniqChar(String s) { if (null == s || s.isEmpty()) { return -1; } int[] nums = new int[26]; char[] chars = s.toCharArray(); for (char a : chars) { nums[a - 'a']++; } for (int i = 0; i < chars.length; i++) { if (1 == nums[chars[i] - 'a']) { return i; } } return -1; } ``` **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(n)。 第二种思路变种：以空间换时间。以新定义字母表数组替换不确定的字符串转换的字符数组。这样的话会大大的节省执行时间。 第二种思路变种代码： ``` public int firstUniqChar(String s) { int[] nums = new int[26]; int[] sum = new int[26]; char[] chars = s.toCharArray(); for( int i = 0; i < chars.length; i++ ) { char a = chars[i]; if (nums[a - 'a'] == 0) { sum[a - 'a'] = i; } nums[a - 'a']++; } int firstLonely = Integer.MAX_VALUE; for (int i = 0; i < 26; i++) { if (nums[i] == 1) { firstLonely = Math.min(sum[i], firstLonely); } } return firstLonely == Integer.MAX_VALUE? -1 : firstLonely; } ``` **复杂度分析** 时间复杂度：O(n)。 空间复杂度：O(n)。 第三种思路：字母表法，同时利用字符串类的indexOf()，lastIndexOf()方法获取特定字符的位置，这两种方法已被Java开发者优化。 第三种思路代码： ``` public int firstUniqChar(String s) { int res = -1; for (char ch = 'a'; ch <= 'z'; ch++) { int index = s.indexOf(ch); if (index != -1 && index == s.lastIndexOf(ch)) { res = res == -1 ? index : Math.min(res, index); } } return res; } ``` **复杂度分析** 不做分析。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**