前端面试算法高频题整理
面向国内前端工程师社招面试。每道题按「思路 → 代码 → 复杂度」整理，不追求覆盖全部 LeetCode，只保留前端面试高频题。
复习建议
- 遇到一道题，先说清楚：暴力解法是什么、为什么慢、如何优化、时间和空间复杂度。
- 重点掌握：哈希表、双指针、滑动窗口、快慢指针、递归、二分查找。
一、排序算法
快速排序
选一个基准值（pivot），把数组划分成「比它小」和「比它大」两部分，递归对两部分分别排序。
function quickSort(arr) {
if (arr.length <= 1) return arr;
const [pivot, ...rest] = arr;
const left = rest.filter(n => n < pivot);
const right = rest.filter(n => n >= pivot);
return [...quickSort(left), pivot, ...quickSort(right)];
}
平均时间复杂度 O(n log n)，最坏情况（数组本身有序，每次都选到最小/最大值当基准）退化到 O(n²)。
归并排序
把数组不断二分到只剩一个元素，再两两合并成有序数组。
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
const result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
result.push(left[i] <= right[j] ? left[i++] : right[j++]);
}
return [...result, ...left.slice(i), ...right.slice(j)];
}
时间复杂度稳定 O(n log n)，不会像快排一样因为数据分布退化，代价是需要额外的合并数组空间，空间复杂度 O(n)。
二、数组与哈希
两数之和
暴力解法是双重循环枚举两个数字，时间复杂度 O(n²)。优化方式是用 Map 保存已经遍历过的数字：遍历当前数字时计算 target - 当前数字，如果 Map 中已经存在这个值，说明找到答案——核心思想是用空间换时间。
function twoSum(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i];
if (map.has(need)) {
return [map.get(need), i];
}
map.set(nums[i], i);
}
return [];
}
时间复杂度 O(n)，空间复杂度 O(n)。
移动零
使用快慢指针：fast 负责遍历数组寻找非零元素，slow 指向下一个非零元素应该放置的位置。找到非零元素后与 slow 位置交换，一次遍历完成原地修改。
function moveZeroes(nums) {
let slow = 0;
for (let fast = 0; fast < nums.length; fast++) {
if (nums[fast] !== 0) {
[nums[slow], nums[fast]] = [nums[fast], nums[slow]];
slow++;
}
}
return nums;
}
时间复杂度 O(n)，空间复杂度 O(1)。
盛水最多的容器
给一个数组表示每根柱子的高度，任选两根柱子和 x 轴构成的容器，求能盛的最大水量。用双指针从两端向中间收拢：容器容量由较矮的柱子决定，所以每次移动较矮的那根指针——移动较高的那根，宽度变小、高度上限不变，面积只会变小，没有尝试的必要。
function maxArea(height) {
let left = 0, right = height.length - 1, max = 0;
while (left < right) {
const area = Math.min(height[left], height[right]) * (right - left);
max = Math.max(max, area);
height[left] < height[right] ? left++ : right--;
}
return max;
}
时间复杂度 O(n)，空间复杂度 O(1)。
三、字符串与滑动窗口
最长无重复字符子串
暴力方式需要枚举所有子串，再判断是否存在重复字符。滑动窗口的思路是：right 不断扩大窗口，出现重复字符时移动 left 收缩窗口，保证窗口内没有重复字符——每个字符最多进入和移出窗口一次。
function lengthOfLongestSubstring(s) {
const set = new Set();
let left = 0;
let max = 0;
for (let right = 0; right < s.length; right++) {
while (set.has(s[right])) {
set.delete(s[left]);
left++;
}
set.add(s[right]);
max = Math.max(max, right - left + 1);
}
return max;
}
时间复杂度 O(n)，空间复杂度 O(k)。
四、链表
反转链表
核心是修改链表指针方向，需要三个变量：prev（当前节点前一个节点）、curr（当前节点）、next（当前节点下一个节点）。步骤：先保存 next 避免断链，再把 curr.next 指向 prev，最后三个指针一起向后移动。
function reverseList(head) {
let prev = null;
let curr = head;
while (curr) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
时间复杂度 O(n)，空间复杂度 O(1)。
判断链表是否有环
使用快慢指针：slow 每次走一步，fast 每次走两步。如果存在环，fast 最终会追上 slow；如果不存在环，fast 会先到达链表尾部。
function hasCycle(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
return true;
}
}
return false;
}
时间复杂度 O(n)，空间复杂度 O(1)。
五、二叉树
二叉树遍历
二叉树遍历本质是递归，区别只在于访问根节点的时机：前序是根→左→右，中序是左→根→右，后序是左→右→根。
function preorder(root, result = []) {
if (!root) return result;
result.push(root.val);
preorder(root.left, result);
preorder(root.right, result);
return result;
}
中序、后序只需调整 result.push(root.val) 这一行相对左右递归调用的位置。时间复杂度 O(n)，空间复杂度 O(h)（h 为树高，对应递归调用栈深度）。
层序遍历
广度优先，用队列。levelSize 记录进入这一层循环之前队列里有多少个节点，用来按层分组输出，不这样做只能拿到打平的遍历结果。
function levelOrder(root) {
if (!root) return [];
const result = [];
const queue = [root];
while (queue.length) {
const levelSize = queue.length;
const level = [];
for (let i = 0; i < levelSize; i++) {
const node = queue.shift();
level.push(node.val);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
result.push(level);
}
return result;
}
时间复杂度 O(n)，空间复杂度 O(n)（最坏情况下队列里要装下一整层节点）。
二叉树最大深度
递归定义：当前节点高度 = 1 + 左右子树最大高度。
function maxDepth(root) {
if (!root) return 0;
return Math.max(
maxDepth(root.left),
maxDepth(root.right)
) + 1;
}
时间复杂度 O(n)，空间复杂度 O(h)。
六、递归与回溯
全排列
回溯三部曲：选一个可能性 → 递归探索基于这个选择的所有可能 → 撤销这个选择，换下一个可能性继续尝试。used 数组标记某个数字在当前路径里是否已经用过，避免重复使用同一个位置的数字。
function permute(nums) {
const result = [];
const path = [];
const used = new Array(nums.length).fill(false);
function backtrack() {
if (path.length === nums.length) {
result.push([...path]);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
path.push(nums[i]);
used[i] = true;
backtrack();
path.pop();
used[i] = false;
}
}
backtrack();
return result;
}
时间复杂度 O(n × n!)，空间复杂度 O(n)（递归栈 + path，不含存储结果本身的开销）。
七、动态规划
斐波那契数列
暴力递归直接照搬定义 f(n) = f(n-1) + f(n-2)，但 f(n-2) 会在算 f(n-1) 和 f(n) 时被重复计算，且重复量随 n 增大指数级膨胀，时间复杂度 O(2ⁿ)。
function fibNaive(n) {
if (n <= 1) return n;
return fibNaive(n - 1) + fibNaive(n - 2);
}
优化思路是把算过的子问题存起来，不重复算。记忆化递归（自顶向下）用一个 Map 缓存已经算过的结果：
function fibMemo(n, memo = new Map()) {
if (n <= 1) return n;
if (memo.has(n)) return memo.get(n);
const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
memo.set(n, result);
return result;
}
时间复杂度降到 O(n)，空间复杂度 O(n)（缓存 + 递归栈）。更常用的是自底向上迭代版，只用两个变量滚动保存前两项，空间复杂度压到 O(1)：
function fib(n) {
if (n <= 1) return n;
let prev2 = 0, prev1 = 1;
for (let i = 2; i <= n; i++) {
const curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
被要求"手写斐波那契"时通常直接写迭代版；被问"怎么优化一个暴力递归"时，讲出暴力递归 → 记忆化 → 迭代这三步演进，比直接甩最优解更能体现对动态规划的理解。
爬楼梯
每次可以爬 1 或 2 级台阶，爬到第 n 级有多少种方法。状态转移方程 f(n) = f(n-1) + f(n-2)，和上面斐波那契的递推关系完全一样，只是初始值不同，同样只用两个变量滚动保存前两个状态，空间复杂度压到 O(1)。
function climbStairs(n) {
if (n <= 2) return n;
let prev2 = 1, prev1 = 2;
for (let i = 3; i <= n; i++) {
const curr = prev1 + prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
时间复杂度 O(n)，空间复杂度 O(1)。
最长递增子序列（LIS）
dp[i] 定义为「以第 i 个元素结尾的最长递增子序列长度」，这是这道题的关键——枚举 i 之前的每个 j，如果 nums[j] < nums[i]，说明 nums[i] 可以接在以 nums[j] 结尾的子序列后面。
function lengthOfLIS(nums) {
const dp = new Array(nums.length).fill(1);
let max = 1;
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
max = Math.max(max, dp[i]);
}
return max;
}
时间复杂度 O(n²)，空间复杂度 O(n)；存在基于二分查找的 O(n log n) 解法，被追问"能否优化"时可以提一句，不强制要求手写。
背包问题（了解思路即可）
0/1 背包：每件物品选或不选，求不超过背包容量下能装的最大价值。dp[i][w] 表示「考虑前 i 件物品、背包容量为 w 时能装的最大价值」，状态转移是「不装第 i 件 dp[i-1][w]」和「装第 i 件 dp[i-1][w-weight[i]] + value[i]」取较大值。前端面试很少要求现场手写完整实现，能识别出"这是背包问题的变体"、说得出这个模型即可。
八、二分查找
标准二分查找
适用于有序数组。每次比较中间元素：相等则返回结果，中间值小于目标则搜索右半部分，中间值大于目标则搜索左半部分——每次排除一半数据。
function binarySearch(nums, target) {
let left = 0;
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] === target) {
return mid;
}
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
时间复杂度 O(log n)，空间复杂度 O(1)。
九、栈与队列
有效括号
利用栈「后进先出」的特性天然匹配括号「最近打开的要最先闭合」这个规则。遍历字符串，遇到左括号就入栈，遇到右括号就检查栈顶是否是与之匹配的左括号。
function isValid(s) {
const stack = [];
const pairs = { ')': '(', ']': '[', '}': '{' };
for (const char of s) {
if (char === '(' || char === '[' || char === '{') {
stack.push(char);
} else {
if (stack.pop() !== pairs[char]) return false;
}
}
return stack.length === 0;
}
stack.pop() 在栈已经空时返回 undefined，自然会和任何 pairs[char] 都不相等，不需要额外判断栈是否为空。遍历完还有没闭合的左括号残留在栈里，也是不合法的，所以最后要检查 stack.length === 0。时间复杂度 O(n)，空间复杂度 O(n)。
十、面试冲刺顺序
第一优先级
- 两数之和
- 移动零
- 最长无重复字符子串
- 反转链表
- 判断链表是否有环
- 二叉树遍历
- 二叉树最大深度
- 标准二分查找
第二优先级
- 盛水最多的容器
- 有效括号
- 层序遍历
- 斐波那契数列
- 爬楼梯
- 全排列
第三优先级（了解即可）
- 快速排序
- 归并排序
- 最长递增子序列（LIS）
- 背包问题