计算机基础 · 共 4 个专题
计算机基础 4 专题 · 11 题

算法与数据结构

复杂度与解题套路

覆盖复杂度口述、双指针与哈希表选型的高频算法面试问答。

2 道题 约 4 分钟 计算机基础 · 算法与数据结构

算法题不只看能不能写出来,更看你能不能把变量、复杂度和选型讲清楚。先给结论,再补边界和替代方案。

Q1

面试里怎么口述时间复杂度和空间复杂度?

基础

一句话回答: 先给最坏情况量级,再点明主导项和变量含义, 最后补空间与优化; 不要只报 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 对小数组用插入排序。

#复杂度#面试表达
Q2

双指针和哈希表怎么选?各自适合什么场景?

高频

一句话回答: 先看是否有序、是否要原地、是否要返回下标; 能排序且要 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²)?—— 固定一个数后, 另外两个数用双指针线性扫。

#双指针#哈希表#选型