前端算法面试专题学习路线

从读题到可证明实现

⚡ 30 秒速记

• 先明确输入规模、数据范围、是否有序、能否修改原数据和重复值语义，再选择数据结构与算法
• 面试表达按「暴力基线 → 可利用性质 → 优化方案 → 循环不变量 / 递归定义 → 复杂度」推进
• 数组常配双指针、滑窗和哈希；树图先定遍历顺序与 visited；最短路、回溯、动态规划各有明确适用信号
• 写代码时先约定函数契约和边界用例，维护可说清的循环不变量，避免“凭感觉把样例跑通”
• 复杂度要说明最坏/均摊条件与额外空间，递归栈、切片、排序和哈希冲突都不能从成本里消失

拿到算法题，我会先确认输入输出、规模、数据范围、有序性、重复值语义以及能否修改原数据，再决定算法和数据结构。 先写出正确的暴力解，才能看清重复计算或无效扫描，从而自然推导出优化方案。编码时要说清循环不变量或递归返回值，例如 twoSum 中，进入第 i 轮时，seen 始终保存 [0, i) 的值与索引。最后补齐空输入、重复值、极端规模等边界，并说明最坏或均摊复杂度，递归栈、排序和哈希代价也要算进去。

拿到题目先复述输入输出，并主动问清规模和边界。规模决定 O(n²) 是否可接受，有序性决定能否二分，值域决定能否计数或用位图，是否允许原地修改则影响空间方案。先给出正确的暴力解能建立基线，再指出重复计算、无效扫描或可复用状态，优化才有推导过程。

编码时要能说出不变量。例如快速排序分区过程中，可以约定 [lo, i) 始终小于 pivot，[i, j) 是已扫描但不小于 pivot 的区间，[j, hi) 尚未处理；每一步交换都维护这个命题。这样正确性来自可检查的状态，而不是“最后看起来排好了”。上面的播放器允许替换输入、逐帧、回退和拖动进度，代码行、指针与数组状态来自同一次真实算法演算。

测试至少覆盖空输入、单元素、全相等、已排序、逆序、重复值和极端规模。复杂度回答也必须带条件：快排平均 O(n log n)、最坏 O(n²)，递归栈平均 O(log n)；若 pivot 选择或输入分布会触发退化，就要说明随机化、三数取中或改用 introsort 等工程策略。

function twoSum(nums, target) {
  const seen = new Map()
  for (let i = 0; i < nums.length; i += 1) {
    const need = target - nums[i]
    if (seen.has(need)) return [seen.get(need), i]
    seen.set(nums[i], i)
  }
  return []
}

这段实现的不变量是：进入第 i 轮时，seen 保存了 [0, i) 的值到索引映射，所以只需检查当前值的补数是否已经出现。时间复杂度期望为 O(n)，额外空间为 O(n)；若题目要求所有答案、排序后下标或值域极大，还要重新确认返回契约与哈希结构的代价。