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

题目

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

案例:

s = "leetcode"
返回 0.

s = "loveleetcode",
返回 2.

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/first-unique-character-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

• 暴力法,双重遍历,时间复杂度O(n^2)
• 使用map,要注意map中的containsKey的操作是O(n),所以会将放入的变成O(n^2),所以会很慢.
• 使用数组来做,同上一道题.

代码

• 暴力法

class Solution {
    public int firstUniqChar(String s) {
        //暴力法,双重遍历,时间复杂度O(n^2)
        if(s == null || s.length() == 0){
            return -1;
        }
        char[] chars = s.toCharArray();
        for(int i =0;i<chars.length;i++){
            char curr = chars[i];
            boolean flag = true;
            for(int j = 0;j< chars.length;j++){
                if(chars[j] == curr && i != j){
                    flag = false;
                    break;
                }
            }
            if(flag){
                return i;
            }
        }
        return -1;
    }
}

• 使用map

class Solution {
    public int firstUniqChar(String s) {
        //使用map解决
        if(s == null || s.length() == 0){
            return -1;
        }
        HashMap<Character,Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        for(int i = 0;i< s.length();i++){
            if(map.get(s.charAt(i)) == 1){
                return i;
            }
        }
        return -1;
    }
}

• 使用数组

class Solution {
   public static int firstUniqChar(String s) {
        int[] letter=new int[26];
        for (char c:s.toCharArray()){
            letter[c-'a']++;   
        }
        for (int i = 0; i <s.length() ; i++) {
            if(letter[s.charAt(i)-'a']==1) return i;
        }
        return -1;
    }
}