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

# 从读题到可证明实现

⚡ 30 秒速记

先问清楚：规模、值域、是否有序、能不能改原数组、重复值怎么算 → 这些直接决定算法
表达顺序：暴力解 → 它浪费在哪 → 利用什么性质优化 → 不变量 → 复杂度
规模估算：n ≤ 10^4 时 O(n²) 一般能过，10^5 以上要往 O(n log n) / O(n) 想
写代码要能说出不变量，比如 twoSum 里「进入第 i 轮时，seen 存的是 [0, i)」
复杂度带条件说：快排平均 O(n log n)、最坏 O(n²)；递归栈、排序、哈希的额外空间都要算

拿到题我不会马上写，先花一分钟问清输入规模、数据范围和边界，因为这些直接决定该用什么解法。 比如有序就能二分，值域小就能计数，能改原数组才能原地交换。然后先说一个暴力解当基线，指出它重复算了什么，优化就有了来路，不是凭空冒出来的。写的时候我会把不变量讲出来，比如 twoSum 里 seen 永远存着当前下标之前的值，这样正确性是讲得清的，不是「样例跑过了」。最后补边界用例，复杂度说清楚是平均还是最坏。

function twoSum(nums, target) {
  const seen = new Map() // 不变量：存的是 [0, i) 的值 -> 下标
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i]
    if (seen.has(need)) return [seen.get(need), i]
    seen.set(nums[i], i)
  }
  return []
}
twoSum([3, 3], 6) // [0, 1]，先查再存，同一个元素不会用两次

拿到题目先复述输入输出，并主动问清规模和边界。规模决定 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 []
}