3 数据结构与算法高频题
数据结构与算法是面试中区分度最高的模块。大厂考察重点不再是“会不会解”，而是“能否在时间、空间约束下选择最优策略，并写出边界完备的代码”。本章提炼三个必考高频题，并附回答框架、追问路径及避坑指南。
面试问答卡片
问题：两数之和（Two Sum）
面试官考察点：
- 是否掌握哈希表空间换时间的思想
- 能否用一次遍历完成，并处理重复元素
- 边界意识：无解时返回什么
回答框架：
- 明确输入：整数数组 + 目标值，返回下标
- 用哈希表记录
值:索引，遍历时检查target - nums[i]是否存在 - 复杂度：时间 O(n)，空间 O(n)
- 注意：不能取同一个元素，先查表再插入
简短示例回答：“使用哈希表，遍历数组时对每个元素计算补数，若补数已在表中则直接返回两个下标，否则将当前元素加入表。一次遍历完成，时间 O(n)，空间 O(n)。”
可能追问：
- 如果数组有序，能否优化空间到 O(1)？
- 要求返回所有不重复解？
- 如果数组超大，内存受限怎么办？
避坑提醒：“不要先全部入表再查找，否则可能重复使用同一个元素。表结构用 dict 而非 list，否则查找退化为 O(n)。”
问题：反转链表（迭代 & 递归）
面试官考察点：
- 链表指针操作熟练度，是否能现场画图推导
- 递归理解：函数栈与返回后指针拼接
- 边界处理：空链表 / 单节点
回答框架：
- 迭代：三指针（prev/curr/next）依次反转指向，最后返回 prev
- 递归：反转 head.next 得到 new_head，再将 head 接到 tail 后面，返回 new_head
- 复杂度均为 O(n) 时间，迭代 O(1) 空间，递归 O(n) 栈空间
简短示例回答：“迭代法：维护 prev 和 curr，每次先保存 next 节点，再将 curr.next 指向 prev，然后移动 prev/curr。递归法：base case 为空或单节点，否则递归反转子链表，再让 head.next.next = head, head.next = None。”
可能追问：
- 反转前 N 个节点？
- K 个一组反转？
- 递归函数调用栈深度过多有什么风险？
避坑提醒：“迭代时容易丢失 next 引用，务必先保存再改指针。递归要注意出口（空或单节点），防止死循环。Python 递归深度默认 1000，超长链表慎用递归。”
问题：括号匹配（有效括号）
面试官考察点：
- 栈的基本应用，是否理解“后进先出”匹配规则
- 是否能处理多种括号共存
- 边界条件：空字符串、奇数长度、右括号多余
回答框架：
- 建立括号映射（右括号到左括号）
- 遍历字符串：左括号入栈，右括号检查栈顶是否匹配
- 遍历结束后栈为空则有效，否则无效
- 复杂度：时间 O(n)，空间 O(n)
简短示例回答：“用栈存储左括号，遇到右括号时若栈空或不匹配则返回 False；否则出栈。遍历完成若栈空为 True。利用字典映射右括号到左括号可简化 if-else。”
可能追问：
- 要求输出最长有效括号子串长度？
- 允许通配符 '*' 的括号匹配？
- 空间能否优化到 O(1)（仅一种括号时）？
避坑提醒：“不要遗漏『栈已空但还遇到右括号』的情况；处理多种括号时映射关系要正确（如 ']' 对应 '['）。if 判断顺序：先检查栈是否空，再检查 top 是否匹配。”