题目描述
思路解析动画文字版
重复计数太浪费。频率表可以把“每个字符出现几次”一次性记下来。
1. 读入字符串：在 "google" 里找第一个只出现一次的字符，返回它的下标。难点：看到一个字符时，还不知道它后面会不会再出现。
2. 两遍法思路：两遍扫描：第一遍数出每个字符的出现次数（存进 cnt），第二遍按原顺序找第一个次数为 1 的。
3. 计数 · g：第一遍开始。第 1 个字符 g，cnt[g]=1。
4. 计数 · o：o，cnt[o]=1。
5. 计数 · o：又一个 o，cnt[o] 加到 2。
6. 计数 · g：又一个 g，cnt[g] 加到 2。
7. 计数 · l：l，cnt[l]=1。
8. 计数 · e：e，cnt[e]=1。第一遍结束。
9. 完整频率：完整频率：g、o 各 2 次，l、e 各 1 次。接下来第二遍，按原字符串顺序找第一个次数为 1 的。
10. 定位 · 下标0 g：第二遍开始。下标 0 的 g：cnt[g]=2，重复，跳过。
11. 定位 · 下标1 o：下标 1 的 o：cnt[o]=2，跳过。
12. 定位 · 下标2 o：下标 2 又是 o，cnt[o]=2，跳过。
13. 定位 · 下标3 g：下标 3 又是 g，cnt[g]=2，跳过。
14. 定位 · 下标4 l 命中：下标 4 的 l：cnt[l]=1，是从左往右第一个唯一字符，返回下标 4。
15. 返回 4：返回 4。两遍线性扫描，时间 O(n)；cnt 表存不同字符，空间 O(k)（小写字母 ≤26）。
这题最容易漏的是“第一个”。只知道谁出现一次还不够，还要按原字符串顺序返回最靠前的位置。
参考代码
class Solution: def firstUniqChar(self, s): cnt = {} for ch in s: cnt[ch] = cnt.get(ch, 0) + 1 for i, ch in enumerate(s): if cnt[ch] == 1: return i return -1复杂度
- 时间复杂度：O(n)，第一遍计数 O(n)，第二遍定位 O(n)。
- 空间复杂度：O(k)，cnt 存不同字符，k=不同字符数；小写字母时 k≤26。
易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最长回文子串
LeetCode 5 · 中等 · 沿着 字符串套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题