前端需要掌握的算法

第一层：基础必备（面试必考，日常常用）

这一层是算法思维的基石，也是前端面试中出现频率最高的部分。

1. 递归 (Recursion)

• 核心：前端算法之魂。树形结构的处理几乎都依赖递归。
• 要点：必须理解递归三要素——终止条件、递推公式、返回值。同时要警惕栈溢出风险（递归深度过大）。
• 典型场景：深拷贝、树形菜单渲染、扁平数组转树、DOM 节点遍历。

2. 排序算法 (Sorting)

• 必须掌握的：
  • 快速排序 (Quick Sort)：V8 引擎 Array.prototype.sort 底层使用的核心算法（当数组长度大于 10 时）。理解分治思想和原地排序。
  • 归并排序 (Merge Sort)：稳定排序，适合链表排序和需要稳定性的场景。
• 了解原理的：
  • 冒泡/选择/插入排序：理解其 O(n²) 的时间复杂度，知道为什么大数据量下不用。
  • 堆排序：结合堆数据结构理解，用于 Top K 问题。
• 关键点：不仅要会写，更要理解稳定性和时间复杂度，以及 JavaScript 中 sort 方法的底层实现差异（不同浏览器引擎实现不同）。

3. 二分查找 (Binary Search)

• 核心：在有序数组中高效查找，时间复杂度 O(log n)。
• 场景：查找某个元素、查找插入位置、查找边界（第一个大于等于目标值的位置）。
• 关键：注意边界条件（left < right 还是 left <= right），避免死循环。

---

第二层：数组与字符串操作（高频业务场景）

这部分是前端日常处理数据时最常用的算法技巧。

4. 双指针 (Two Pointers)

• 核心：用两个指针（快慢指针、左右指针）在一次遍历中解决问题，降低时间复杂度。
• 场景：
  • 左右指针：两数之和（有序数组）、反转字符串、回文判断、盛最多水的容器。
  • 快慢指针：删除有序数组中的重复项、环形链表检测（判断链表是否有环）。
• 价值：很多需要 O(n²) 的问题可以用双指针优化到 O(n)。

5. 滑动窗口 (Sliding Window)

• 核心：维护一个窗口（子数组/子串），在遍历过程中动态调整窗口大小。
• 场景：
  • 长度最小的子数组（和 ≥ target）
  • 无重复字符的最长子串（高频面试题）
  • 限制并发请求数量（窗口控制同时进行的请求数）
• 关键：熟练使用 Map 或 Set 配合窗口指针维护窗口内的状态。

6. 哈希表与计数 (Hash Map / Counter)

• 核心：空间换时间，将查找时间从 O(n) 降到 O(1)。
• 场景：
  • 两数之和（经典入门题）
  • 数组去重、交集/并集
  • 字符统计（判断异位词、回文排列）
  • 频率限制（节流防抖的变体、LRU 缓存）

---

第三层：树与递归（前端核心竞争力）

前端是处理树形结构的行家，这部分能力直接决定了你对框架和复杂业务的理解深度。

7. 树的遍历 (Tree Traversal)

• 深度优先遍历 (DFS)：
  • 前序：根 -> 左 -> 右，常用于生成 DOM 树、深拷贝。
  • 中序：左 -> 根 -> 右，二叉搜索树中序遍历得到有序序列。
  • 后序：左 -> 右 -> 根，常用于删除节点、计算子树高度（React 的 useEffect 清理函数就是后序思想）。
• 广度优先遍历 (BFS)：
  • 用队列实现，常用于查找最近节点、层级遍历（树形表格的平铺）。
• 典型题目：二叉树的最大深度、路径总和、二叉树的层序遍历、二叉树的最近公共祖先。

8. 树的构建与转换

• 核心能力：将业务中的扁平数据（如后端返回的列表）转换为树形结构。
• 典型题目：
  • 扁平数组转树：利用 Map 建立 id 到节点的映射，O(n) 复杂度实现，而不是双重循环。
  • 树转扁平数组：递归或栈遍历，用于生成下拉选项或表格数据。
  • 路径求和：找出从根节点到叶子节点路径上所有节点的和。

---

第四层：进阶与工程应用（区分中高级工程师）

这部分算法在前端工程化、性能优化和复杂交互中至关重要。

9. 回溯算法 (Backtracking)

• 核心：暴力穷举的优化版（试错 + 剪枝）。
• 场景：
  • 组合/排列问题：生成所有子集、全排列、组合总和。
  • 路径搜索：迷宫问题、N 皇后（虽然前端不直接写，但思维重要）。
  • 实际应用：权限组合计算、多级联动选择器的状态生成。
• 关键：理解 ” 选择 → 递归 → 撤销选择 ” 这个模板。

10. 动态规划 (Dynamic Programming)

• 定位：前端面试中，动态规划属于 ” 加分项 ” 而非 ” 必选项 “，但大厂面试中常见简单到中等的 DP 题。
• 核心：将大问题拆解为重叠子问题，找到状态转移方程。
• 前端相关场景：
  • 爬楼梯问题：理解斐波那契数列，类比页面的步骤导航。
  • 背包问题：资源分配、预算选择。
  • 最长递增子序列：Vue 3 的 diff 算法优化中就用到了这个算法来找出最长稳定序列，减少 DOM 移动次数。
  • 编辑距离：模糊搜索、拼写建议的底层原理。
• 策略：先掌握递归写法（自顶向下），再优化为迭代 + DP 数组（自底向上）。

11. 贪心算法 (Greedy)

• 核心：每一步都取局部最优，期望得到全局最优。
• 场景：
  • 活动安排：区间调度（不重叠区间的最大数量）。
  • 分发饼干：资源分配问题。
  • 实际应用：合并区间（处理时间冲突）、最少硬币找零（特定货币体系下）。

12. 字符串匹配算法

• 核心：高效地在文本中查找子串。
• 场景：
  • 敏感词过滤、代码搜索、编辑器查找功能。
• 掌握程度：
  • KMP：理解其利用 ” 部分匹配表 ” 避免重复比较的思想即可，手写 KMP 在面试中极少要求。
  • Rabin-Karp：滚动哈希算法，理解其原理有助于理解浏览器或工具中的字符串搜索优化。

---

前端算法学习策略

按面试难度分级

级别	重点内容	典型题目
必会（中小厂/日常）	递归、双指针、哈希表、树的遍历、数组转树	两数之和、反转链表、扁平化数组、深拷贝
进阶（大厂/高级）	滑动窗口、回溯、动态规划（简单 - 中等）、LRU	无重复字符最长子串、全排列、最长递增子序列
加分（架构/专家）	红黑树思想、B+ 树（数据库索引理解）、布隆过滤器	手写 Promise、实现防抖节流（结合算法思想）

学习建议

1. 先数据结构，后算法：算法是数据结构的操作。不理解栈，就没法理解括号匹配；不理解树，就没法理解树的遍历。

2. 代码随想录/LeetCode Hot 100 刷法： - 前端重点刷数组、字符串、链表、树这四类。 - 贪心和动态规划遇到简单和中等题再深入，不必死磕难题。

3. 与前端实际场景结合： - 学递归时，手写一个深拷贝（处理循环引用）。 - 学树遍历时，实现一个递归组件（文件夹树）。 - 学LRU时，实现一个图片缓存管理器。 - 学回溯时，实现一个简单的权限组合选择器。

4. 关注复杂度意识： - 写代码时习惯性问自己：这个循环嵌套循环是 O(n²) 吗？数据量 1000 条时会卡吗？这种 ” 算法思维 ” 比会写具体算法更重要。

5. 善用 JavaScript 特性： - Set 用于去重和集合运算。 - Map 用于缓存和频率统计。 - 尾递归优化（虽然 V8 支持有限，但可以了解）。

总结：前端算法学习，目标不是成为解题机器，而是建立复杂度意识和问题建模能力。当你面对一个复杂的交互需求（如树形表格拖拽排序、实时协作光标位置同步）时，能自然地想到用什么样的数据结构来存储、用什么样的算法来操作，这才是核心竞争力。

---

相关阅读

• 常用算法汇总 — 算法知识汇总
• 递归算法要点总结 — 递归核心要点
• 动态规划 — 动态规划核心概念
• 最优子结构 — 动态规划核心特性
• 重叠子问题 — 动态规划另一核心特性
• 快速排序 — 快速排序详解
• 滑动窗口解题心得 — 滑动窗口解题技巧
• 两数之和 — 哈希表经典应用