复杂度与解题套路
覆盖复杂度口述、双指针与哈希表选型的高频算法面试问答。
算法题不只看能不能写出来,更看你能不能把变量、复杂度和选型讲清楚。先给结论,再补边界和替代方案。
面试里怎么口述时间复杂度和空间复杂度?
基础一句话回答: 先给最坏情况量级,再点明主导项和变量含义, 最后补空间与优化; 不要只报 O(n),要说明 n 是什么。
展开:
- 口述顺序:先说步骤, 再写每步复杂度, 最后合并取主导项; 排序加双指针是 O(n log n) 加 O(n)。
- 变量:n 是数组长度、V 是值域、 E 是边数; 二维 DP 是 O(n·m), 滚动数组压到 O(m)。
- 边界:快排最坏 O(n²)、 平均 O(n log n), 递归栈平均 O(log n); 哈希平均 O(1)、最坏 O(n)。
- 空间:递归栈、结果数组、 哈希表都要算, 别只算输入 n; 字符串循环拼接是 O(n²)。
- 反向:n 小于几十时, 插入排序可能更快, 工程上会设阈值, 不能只看渐进复杂度。
- 常见坑:哈希遍历顺序不稳定, 不能依赖;空间别漏掉 递归栈和结果数组。
追问: O(n log n) 一定比 O(n²) 快吗?—— 不一定, 小 n 时常数占主导,TimSort 对小数组用插入排序。
双指针和哈希表怎么选?各自适合什么场景?
高频一句话回答: 先看是否有序、是否要原地、是否要返回下标; 能排序且要 O(1) 空间用双指针, 无序查存在性用哈希表。
展开:
- 双指针:排序后左右夹逼, 时间 O(n log n)、空间 O(1); 排序会打乱下标, 要额外存值和下标。
- 哈希表:一次遍历查 target 减当前值, 时间 O(n)、空间 O(n), 保留下标。
- 取舍:只判断存在性、 不要下标, 排序加双指针省内存; 要下标或不能改数组, 哈希表更直接。
- 工程:HashMap 默认负载因子 0.75,超了扩容到 2 倍; 双指针注意去重。
- 反向:既要下标又想省内存, 只能排序存副本; 副本仍是 O(n), 真省内存就得放弃下标。
- 边界:三数之和固定一个数后双指针, 从 O(n³) 降到 O(n²);哈希解法要去重。
追问: 三数之和为什么能从 O(n³) 降到 O(n²)?—— 固定一个数后, 另外两个数用双指针线性扫。