当前位置：首页 > news >正文

C/C++哈希表与字符串进阶面试题

news 2026/7/3 14:48:45

题目 1：字母异位词分组

题目描述

给你一个字符串数组，请你将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

解题思路

哈希表分组法：互为异位词的字符串，排序后结果完全相同。以「排序后的字符串」作为 key，原字符串作为 value 存入哈希表，最终将哈希表中的 value 分组输出即可。

代码实现

cpp

运行

vector<vector<string>> groupAnagrams(vector<string>& strs) { unordered_map<string, vector<string>> hash; for (string& s : strs) { string key = s; sort(key.begin(), key.end()); // 排序后作为key hash[key].push_back(s); } vector<vector<string>> res; for (auto& pair : hash) { res.push_back(pair.second); } return res; }

复杂度分析

时间复杂度：O (n * k log k)，n 是字符串数量，k 是字符串最大长度
空间复杂度：O (n*k)，哈希表存储所有字符

面试考点

哈希表的分组应用。面试官常追问：如果字符串很长，排序开销大，有没有更优的 key 生成方式？（可用字符计数数组作为 key）

题目 2：无重复字符的最长子串

题目描述

给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。

解题思路

滑动窗口 + 哈希表：维护一个滑动窗口[left, right]，用哈希表记录字符最后一次出现的索引：

右指针不断向右扩展
遇到重复字符时，将左指针移动到「重复字符上一次出现位置 + 1」和「当前 left」的较大值
每次更新窗口最大长度

代码实现

cpp

运行

int lengthOfLongestSubstring(string s) { unordered_map<char, int> hash; int left = 0; int maxLen = 0; for (int right = 0; right < s.size(); right++) { // 如果字符已在窗口内，更新左边界 if (hash.count(s[right]) && hash[s[right]] >= left) { left = hash[s[right]] + 1; } hash[s[right]] = right; maxLen = max(maxLen, right - left + 1); } return maxLen; }

复杂度分析

时间复杂度：O (n)，右指针只遍历一次
空间复杂度：O (1)，字符集有限（如 ASCII），哈希表大小固定

面试考点

滑动窗口经典题，是字符串高频考点。重点考察窗口边界的维护和重复字符的处理逻辑。

题目 3：第一个只出现一次的字符

题目描述

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。s 只包含小写字母。

解题思路

两次遍历 + 计数数组：因为只有小写字母，用长度为 26 的数组代替哈希表：

第一次遍历：统计每个字符出现的次数
第二次遍历：按顺序检查每个字符的计数，第一个计数为 1 的就是答案

代码实现

cpp

运行

char firstUniqChar(string s) { int count[26] = {0}; for (char c : s) { count[c - 'a']++; } for (char c : s) { if (count[c - 'a'] == 1) { return c; } } return ' '; }

复杂度分析

时间复杂度：O (n)，两次线性遍历
空间复杂度：O (1)，固定大小的计数数组

面试考点

考察数组代替哈希表的优化思想。延伸问：如果字符范围很大怎么办？如果是流数据无法二次遍历怎么办？

题目 4：字符串转整数（atoi）

题目描述

请你来实现一个myAtoi(string s)函数，使其能将字符串转换成一个 32 位有符号整数。需要处理：前导空格、正负号、溢出截断、非数字字符提前终止等情况。

解题思路

按步骤处理：

跳过前导空格
判断正负号，记录符号位
逐位转换数字，每一步检查是否溢出
溢出时根据符号返回 INT_MAX 或 INT_MIN

代码实现

cpp

运行

int myAtoi(string s) { int i = 0; int sign = 1; long res = 0; // 用long暂存，方便判断溢出 // 1. 跳过空格 while (i < s.size() && s[i] == ' ') i++; // 2. 处理符号 if (i < s.size() && (s[i] == '+' || s[i] == '-')) { sign = (s[i] == '-') ? -1 : 1; i++; } // 3. 转换数字 while (i < s.size() && isdigit(s[i])) { res = res * 10 + (s[i] - '0'); // 溢出判断 if (res * sign >= INT_MAX) return INT_MAX; if (res * sign <= INT_MIN) return INT_MIN; i++; } return res * sign; }