企业官网建设流程全解析

• 文档
• 教程
• 知识库

本文是 InterviewGuide 仓库《带你快速刷完67道剑指offer》专栏中 No34 第一个只出现一次的字符 的完整技术题解。该题对应牛客网剑指 Offer 专题第 34 题，是一道典型的「字符频率统计 + 顺序扫描」入门题，几乎每一位 C++ 求职者在刷题初期都会遇到。读完本文你将掌握：基于定长数组与unordered_map的两种计数实现、各自的时间/空间复杂度差异，以及如何将同一套思路迁移到字符流、LeetCode 变体等进阶场景，做到「一道题吃透一类题」。

题目描述与示例

在一个字符串（0 <= 字符串长度 <= 10000，全部由字母组成）中找到第一个只出现一次的字符，并返回它的位置，如果没有则返回-1（需要区分大小写），位置从 0 开始计数。

示例 1

• 输入："google"
• 返回值：4

对输入做拆解可以直观理解题意：

其中l是第一个（按下标顺序）只出现一次的字符，因此返回其下标4。注意e也只出现一次，但它位于l之后，不满足「第一个」的要求——这正是本题的核心考点：不仅要统计频次，还要保持原始字符串的顺序来判定先后。

解法一：定长数组计数（推荐，O(1) 空间）

这是原题解给出的第一种做法，也是面试中最容易被面试官认可的写法：

int FirstNotRepeatingChar(string str) { vector<int> result(58, 0); for (int i = 0; i < str.size(); ++i) { result[str[i] - 'A'] += 1; } for (int i = 0; i < str.size(); ++i) { if (result[str[i] - 'A'] == 1) return i; } return -1; }

为什么数组长度是 58？

这是该解法最值得展开讲解的细节。题目限定字符串全部由字母组成且区分大小写，即字符集为A-Z与a-z，共 52 个字符。在 ASCII 编码中：

• 'A'的 ASCII 码为 65，'z'的 ASCII 码为 122；
• 若以'A'为基准做下标映射（str[i] - 'A'），下标范围是0 ~ 122-65 = 57；
• 因此分配58个槽位即可覆盖整个A-Z+a-z区间，其中91 ~ 96（[ \ ] ^ _ ``）之间的 6 个 ASCII 字符永远不会被用到，属于预留空隙。

这一「用下标做字符映射的定长计数数组」技巧，本质上是把字符当作小整数使用，从而避免引入哈希结构，是 C/C++ 风格算法题中最经典的空间换时间的写法之一。它天然支持大小写区分：'a' - 'A'与'A' - 'A'落在不同下标，互不干扰。

算法流程与复杂度

1. 第一遍扫描：遍历字符串，对每个字符执行result[str[i] - 'A'] += 1，统计各字符出现次数；
2. 第二遍扫描：再次按下标从小到大遍历原始字符串，返回第一个计数恰为 1 的字符下标；若不存在则返回-1。

• 时间复杂度：O(n)，其中n为字符串长度（n <= 10000），两轮线性扫描；
• 空间复杂度：O(1)，无论输入多长，数组大小恒为 58。

之所以必须扫描两遍，是因为第一遍只负责统计，而「第一个只出现一次」要求按字符在字符串中首次出现的顺序判定，这与vector/unordered_map内部元素的存储顺序无关，只能通过第二次对原始字符串的顺序遍历来确定。

解法二：unordered_map 哈希计数

原题解给出的第二种做法，适用于字符集不确定或字母范围之外字符较多的一般化场景：

int FirstNotRepeatingChar(string str) { unordered_map<char, int> mp; for (int i = 0; i < str.size(); ++i) { mp[str[i]] += 1; } for (int i = 0; i < str.size(); ++i) { if (mp[str[i]] == 1) return i; } return -1; }

实现要点

• unordered_map<char, int>以字符为键、出现次数为值，只对实际出现过的字符分配存储空间，不会像 58 槽数组那样存在预留空隙；
• 使用mp[str[i]] += 1时，若键不存在，operator[]会先以默认值0插入该键再自增，因此无需手动insert；
• 第二轮顺序遍历字符串，命中mp[str[i]] == 1立即返回下标，逻辑与解法一完全一致。

复杂度对比

• 时间复杂度：O(n)，unordered_map单次操作平均O(1)，整体仍是线性；
• 空间复杂度：O(k)，k为字符串中实际出现的不同字符数，最坏情况下（52 种字母全部出现）为O(52)，仍是常数级别，但常数因子大于解法一的固定 58 槽。

在本题「全部由字母组成」的约束下，解法一在常数性能与代码简洁度上略优；解法二的优势在于通用性——把char换成任意可哈希类型（如int、string），即可无缝扩展到非字母字符集场景。

二刷解法：精简版 unordered_map

原题解记录了阿秀二刷时的实现，思路与解法二相同，代码更加精简，可作为面试默写模板：

int FirstNotRepeatingChar(string str) { unordered_map<char, int> unmp; // char -> count for (int i = 0; i < str.size(); ++i) unmp[str[i]]++; for (int i = 0; i < str.size(); ++i) if (unmp[str[i]] == 1) return i; return -1; }

与解法二的差异仅在于命名与写法风格（使用++自增、注释更少），算法本质完全相同。这一版本也印证了该题「计数 + 顺序扫描」的两遍式模板在反复刷题中的稳定性：掌握一个通用骨架，就能稳定复现。

三种实现对比与面试作答要点

面试官追问时建议围绕以下几点组织回答：

1. 为什么是两遍扫描：第一遍建立「字符 → 次数」的统计表；第二遍沿原始顺序找到第一个计数为 1 的字符。计数结构本身不保序，必须依赖原字符串顺序；
2. 58 的由来：'A'=65、'z'=122，122 - 65 + 1 = 58，覆盖A-Z与a-z；
3. 大小写敏感的天然支持：'a'与'A'映射到不同下标/键，互不干扰，无需额外处理；
4. 边界情况：空字符串直接返回-1；全重复字符串（如"aabb"）两遍扫描后无命中，返回-1。

同类题拓展：从静态字符串到字符流

掌握了静态字符串的解法后，可以顺势迁移到本专栏的姊妹题 No54 字符流中第一个不重复的字符。该题要求在一个动态增长的字符流中实时返回「当前第一个只出现一次的字符」，若不存在返回#。原题解借助vector<char>记录字符到达顺序、unordered_map记录频次，核心思想与本题完全同源：

class Solution { public: void Insert(char ch) { v.push_back(ch); unmp[ch]++; // 边插入边计数 } char FirstAppearingOnce() { for (auto &ch : v) { // 沿到达顺序找第一个频次为 1 的字符 if (unmp[ch] == 1) return ch; } return '#'; } vector<char> v; unordered_map<char, int> unmp; };

两题的差异只在「数据是静态一次给全」还是「随时间动态追加」，解题骨架（顺序容器 + 计数表）完全一致，可以作为一组对照题一起复习。

关联变体与延伸阅读

• LeetCode 387「字符串中的第一个唯一字符」：题解笔记。变体约束为「只包含小写字母」，因此计数数组可进一步压缩为int result[26]，用s[i] - 'a'映射，思路完全一致，适合作为练习题的落地验证；
• No40 数组中只出现一次的数字：题解笔记。同为「只出现一次」家族，但计数场景换成了整型数组，且进阶到「只有两个数字出现一次」，除了哈希计数外还引入了异或（XOR）分组解法，可对比学习「哈希计数」与「位运算」两种思路各自的适用边界；
• 若想系统刷完整个专题，可查看 剑指 Offer 专栏导读 与 67 道剑指 Offer 题解全集（本题全集版见其中 No34 小节）；不确定从哪个专栏入手的话，可先阅读算法模块食用指南。

小结

No34「第一个只出现一次的字符」是哈希计数类题目的最小可复现样本，其「两遍扫描 + 计数结构」模板可直接迁移到字符流、数组、字符串去重等多类高频面试题中。本题的两个关键记忆点：一是计数结构不保序、必须按原串顺序二次扫描；二是在字母集约束下用58槽定长数组可做到严格的 O(1) 空间。建议读者在 InterviewGuide 仓库 原题解基础上，自行补充空串、全重复串、大小写混合串等用例，把这一模板练到可默写、可讲清为止。

• 文档
• 教程
• 知识库