第4章 数据结构与算法高频题
本章聚焦面试中最常考的数据结构与算法题目，包括数组、链表、树、哈希、排序、动态规划。掌握核心思路和回答框架，能帮助你在面试中快速拆解问题、清晰表达方案。
📊 常见数据结构操作时间复杂度对比
| 数据结构 | 存储方式 | 访问（索引） | 插入/删除（头/尾） | 查找 |
|---|---|---|---|---|
| 数组 | 连续内存 | O(1) | O(n) | O(n) |
| 链表（单链） | 非连续指针链接 | O(n) | O(1)（已知位置） | O(n) |
| 哈希表 | 数组+链表/红黑树 | — | O(1)平均 | O(1)平均 |
| 二叉搜索树（平衡） | 树节点 | O(log n) | O(log n) | O(log n) |
| 堆（二叉堆） | 数组模拟完全二叉树 | O(1)（顶） | O(log n) | O(n) |
面试建议：遇到算法题先确定核心数据结构，然后套用经典解法（双指针、滑动窗口、递归DP等），最后注意边界条件。
🧩 面试问题：如何判断一个链表是否有环？
面试官考察点：
- 链表遍历与指针操作基本功
- 双指针（快慢指针）技巧
- 边界条件处理（空链表、单节点）
回答框架：
- 判断链表为空或只有一个节点，直接返回无环。
- 定义快慢指针，快指针每次走两步，慢指针每次走一步。
- 若快慢指针相遇则有环；若快指针走到None则无环。
示例回答：
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False可能追问：
- 如何找到环的入口节点？（快慢指针相遇后，让一个指针从头开始，步长1，再次相遇点即入口）
- 如果链表很长，内存有限怎么优化？（考虑使用集合记录已访问节点，但空间O(n)）
🚨 避坑提醒：忘记检查 fast.next 会造成空指针异常；循环条件必须同时判断 fast 和 fast.next。
🧩 面试问题：给定一个整数数组和一个目标值，找出数组中两个数之和等于目标值的索引。
面试官考察点：
- 哈希表应用（空间换时间）
- 遍历与查表优化
- 对重复元素的处理
回答框架：
- 初始化哈希表，键为元素值，值为索引。
- 遍历数组，对当前元素x，计算补数target-x。
- 若补数已在哈希表中，返回对应索引。
- 否则将当前元素加入哈希表。
示例回答：
def two_sum(nums, target):
seen = {}
for i, val in enumerate(nums):
complement = target - val
if complement in seen:
return [seen[complement], i]
seen[val] = i
return []可能追问：
- 如果数组已排序，如何优化？（双指针法，O(1)空间）
- 如果数组中存在重复元素，怎么保证返回唯一解？（题目通常假定只有唯一解；否则需额外判断）
🚨 避坑提醒：不能先全部存入哈希表再遍历，可能重复使用同一元素（如[3,3] target=6）；必须边遍历边检查。
🧩 面试问题：实现斐波那契数列，要求时间复杂度 O(n) 且空间 O(1)。
面试官考察点：
- 递归 vs 迭代理解
- 动态规划状态压缩思想
- 大数处理意识
回答框架：
- 边界：n=0返回0，n=1返回1。
- 用两个变量a=0,b=1滚动计算。
- 循环n-1次，每次更新a,b为b,a+b。
- 最后返回b。
示例回答：
def fib(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a可能追问：
- n非常大（如10^7）时，Python还能承受吗？（Python大整数无溢出，但速度变慢，可考虑矩阵快速幂）
- 如何用矩阵幂将时间复杂度降到O(log n)？（使用斐波那契矩阵幂）
🚨 避坑提醒：注意循环次数；如果取n=0，应返回a（0），不要返回b；使用递归会导致指数级复杂度，面试时务必主动指出优化方案。