LeetCode字符串中的第一个唯一字符题解-java

题目

难度简单296

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

示例：

s = "leetcode"返回 0s = "loveleetcode"返回 2

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

题解

方法一：哈希表存放字符及其出现次数

思路

遍历一遍字符串，然后将字符串中每个字符及其相应出现的次数存放在一个哈希表中，然后遍历这个字符串，判断在哈希表中出现的次数，若找到第一个出现次数为1时，则返回此时下标

代码实现

class Solution {
       public int firstUniqChar(String s) {
           // 新建一个hashmap散列表用来存放出现的字符及其相应出现的次数        HashMap
   
     hashmap = new HashMap<>();        // 遍历字符串，存放字符及其相应出现的次数        for(int i = 0; i < s.length(); i++){
               if(!hashmap.containsKey(s.charAt(i))){
                   hashmap.put(s.charAt(i), 1);            }else{
                   hashmap.put(s.charAt(i), hashmap.get(s.charAt(i)) + 1);            }        }        // 遍历字符串，遇到第一个字符出现的次数为1时，返回此下标        for(int j = 0; j < s.length(); j++){
               if(hashmap.get(s.charAt(j)) == 1){
                   return j;            }        }        return -1;    }}

复杂度分析

时间复杂度： O(N)只遍历了两遍字符串，同时散列表中查找操作是常数时间复杂度的。

空间复杂度： O(N)用到了散列表来存储字符串中每个元素出现的次数。

提交详情

方法二：

思路

使用一个长度为26的int数组来存放字符出现的次数，数组的下标即对应26个字母

代码实现

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