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

题目描述

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。 示例 1： 输入: s = "leetcode" 输出: 0

示例 2: 输入: s = "loveleetcode" 输出: 2

示例 3: 输入: s = "aabb" 输出: -1 提示: 1 <= s.length <= 10^5 s 只包含小写字母

题目解析

题目在说什么

我们有一个字符串，比如 "leetcode"。里面有很多字母，有些字母只出现了一次，比如 l、t、c、o、d，有些字母出现了多次，比如 e 出现了三次。我们要找到 第一个 只出现一次的字母，然后返回它在字符串里的位置（索引，从0开始数）。如果所有字母都重复了，就返回 -1。

举个例子："loveleetcode"，第一个只出现一次的字母是 v，它在索引 2 的位置（从0开始数：l是0，o是1，v是2）。

思路是怎么来的

想象一下，你有一堆写着字母的卡片，卡片顺序固定，不能打乱。你想找出第一个只出现一次的卡片。

最直接的想法：拿第一张卡片，然后检查后面有没有和它一样的卡片。如果没有，它就是答案；如果有，就跳过它，检查第二张卡片……这样虽然能行，但效率很低——每次都要往后找很久，如果字符串很长，会很慢。

更聪明的办法：我们先不急着找，而是先做一次“人口普查”。把所有卡片都看一遍，记下每个字母出现了几次。比如 "leetcode"，我们记下：l出现1次，e出现3次，t出现1次……这个记录就像一张“频率表”。

有了频率表之后，我们再从头开始看卡片：第一张是 l，查一下频率表，l只出现1次，那它就是答案，直接返回它的位置0。如果第一张是重复的，我们就看第二张，以此类推。

这个方法的好处是：第一次遍历（做频率表）和第二次遍历（找答案）都是只看一遍所有卡片，非常快。

代码逐步拆解

我们来看参考代码（Java），一行一行解释。

class Solution {
    public int firstUniqChar(String s) {
        // 定义一个哈希表，用于统计字符串中每个字符的频率
        int[] cnt = new int[26];

这里定义了一个长度为26的整数数组 cnt。为什么是26？因为题目说字符串只包含小写字母，小写字母一共26个。这个数组就是我们的“频率表”。cnt[0] 对应字母 a 的出现次数，cnt[1] 对应 b，……，cnt[25] 对应 z。

        // 遍历字符串，记录每个字符的出现频率
        for (char c : s.toCharArray()) {
            cnt[c - 'a']++;
        }

这一行是第一次遍历。s.toCharArray() 把字符串变成字符数组，比如 "abc" 变成 ['a','b','c']。然后对于每个字符 c，我们做 cnt[c - 'a']++。

这里 c - 'a' 是一个小技巧：字符在计算机里其实是用数字表示的，'a' 是97，'b' 是98，……。所以 c - 'a' 就能把 'a' 变成0，'b' 变成1，……，正好对应数组的索引。++ 就是让那个位置的值加1，表示这个字母又出现了一次。

比如 "leetcode"，遍历完以后，cnt 数组里：cnt['l'-'a']（即 cnt[11]）变成1，cnt['e'-'a']（即 cnt[4]）变成3，等等。

        // 遍历字符串，找到第一个频率为 1 的字符，返回其下标
        for (int i = 0; i < s.length(); i++) {
            if (cnt[s.charAt(i) - 'a'] == 1) {
                return i;
            }
        }