1. 前端算法实战：从零手撕高频面试题
作为一名经历过多次大厂面试的前端工程师，我深知算法能力在前端面试中的重要性。很多人认为前端不需要算法，但现实是各大厂的前端岗位面试中，算法题占比越来越高。今天我就来分享几个前端面试中最常考的算法题，带你从零理解解题思路，掌握最优解法。
2. 无重复字符的最长子串
2.1 问题分析
给定一个字符串，找出其中不含有重复字符的最长子串的长度。例如：
- 输入："abcabcbb"，输出：3（"abc"）
- 输入："bbbbb"，输出：1（"b"）
2.2 滑动窗口解法
最优解法是滑动窗口（双指针）算法，时间复杂度O(n)：
var lengthOfLongestSubstring = function(s) { const charIndexMap = new Map(); let left = 0; let maxLength = 0; for (let right = 0; right < s.length; right++) { const currentChar = s[right]; if (charIndexMap.has(currentChar) && charIndexMap.get(currentChar) >= left) { left = charIndexMap.get(currentChar) + 1; } charIndexMap.set(currentChar, right); maxLength = Math.max(maxLength, right - left + 1); } return maxLength; };2.3 关键点解析
- charIndexMap：记录字符最后出现的位置
- 左指针移动：只有当重复字符在当前窗口内时才移动
- 窗口长度计算：right - left + 1
注意事项：处理"abba"这类情况时，左指针不能回退，必须确保left只向右移动
3. 比较版本号
3.1 问题描述
比较两个版本号version1和version2：
- 如果version1 > version2，返回1
- 如果version1 < version2，返回-1
- 否则返回0
3.2 拆分+补零解法
var compareVersion = function(version1, version2) { const v1Arr = version1.split('.'); const v2Arr = version2.split('.'); const maxLen = Math.max(v1Arr.length, v2Arr.length); for (let i = 0; i < maxLen; i++) { const num1 = i < v1Arr.length ? parseInt(v1Arr[i], 10) : 0; const num2 = i < v2Arr.length ? parseInt(v2Arr[i], 10) : 0; if (num1 > num2) return 1; if (num1 < num2) return -1; } return 0; };3.3 核心技巧
- split('.')：正确拆分版本号
- parseInt：自动忽略前导零
- 补零处理：短版本号缺失部分视为0
4. 合并两个有序数组
4.1 逆向双指针解法
从后往前合并，避免覆盖nums1的元素：
var merge = function(nums1, m, nums2, n) { let p1 = m - 1; let p2 = n - 1; let p = m + n - 1; while (p1 >= 0 && p2 >= 0) { nums1[p--] = nums1[p1] >= nums2[p2] ? nums1[p1--] : nums2[p2--]; } while (p2 >= 0) { nums1[p--] = nums2[p2--]; } };4.2 关键点
- 三指针初始化：p1指向nums1有效末尾，p2指向nums2末尾
- 从后往前填充：避免元素覆盖
- 处理剩余元素：只需处理nums2剩余情况
5. 有效的括号
5.1 栈的应用
var isValid = function(s) { const bracketMap = { ')': '(', '}': '{', ']': '[' }; const stack = []; for (let char of s) { if (char in bracketMap) { if (stack.length === 0 || stack.pop() !== bracketMap[char]) { return false; } } else { stack.push(char); } } return stack.length === 0; };5.2 注意事项
- 右括号映射：使用对象快速查找对应左括号
- 栈空检查：遇到右括号时栈不能为空
- 最终栈检查：遍历结束后栈必须为空
6. 字符串相加
6.1 模拟手工加法
var addStrings = function(num1, num2) { let i = num1.length - 1; let j = num2.length - 1; let carry = 0; const result = []; while (i >= 0 || j >= 0 || carry > 0) { const digit1 = i >= 0 ? Number(num1[i--]) : 0; const digit2 = j >= 0 ? Number(num2[j--]) : 0; const sum = digit1 + digit2 + carry; result.push(sum % 10); carry = Math.floor(sum / 10); } return result.reverse().join(''); };6.2 关键步骤
- 从末尾开始相加：模拟手工计算
- 处理进位：carry记录进位值
- 结果反转：因为是从个位开始存储
7. 两数之和
7.1 哈希表最优解
var twoSum = function(nums, target) { const map = new Map(); for (let i = 0; i < nums.length; i++) { const complement = target - nums[i]; if (map.has(complement)) { return [map.get(complement), i]; } map.set(nums[i], i); } return []; };7.2 性能对比
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 暴力法 | O(n²) | O(1) |
| 哈希表法 | O(n) | O(n) |
8. 全排列
8.1 回溯算法
var permute = function(nums) { const result = []; const path = []; const used = new Array(nums.length).fill(false); const 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; };8.2 回溯三要素
- 选择：将元素加入路径
- 递归：继续选择下一个元素
- 撤销：回溯到上一步
9. 反转链表
9.1 迭代法
var reverseList = function(head) { let prev = null; let curr = head; while (curr !== null) { const nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; } return prev; };9.2 递归法
var reverseList = function(head) { if (head === null || head.next === null) { return head; } const newHead = reverseList(head.next); head.next.next = head; head.next = null; return newHead; };10. 二叉树层序遍历
10.1 BFS实现
var levelOrder = function(root) { if (!root) return []; const result = []; const queue = [root]; while (queue.length) { const levelSize = queue.length; const currentLevel = []; for (let i = 0; i < levelSize; i++) { const node = queue.shift(); currentLevel.push(node.val); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } result.push(currentLevel); } return result; };10.2 关键点
- 队列管理：先进先出处理节点
- 层级记录：通过levelSize确保按层处理
- 子节点入队：左节点先入队
11. 最大子数组和
11.1 Kadane算法
var maxSubArray = function(nums) { let currentSum = nums[0]; let maxSum = nums[0]; for (let i = 1; i < nums.length; i++) { currentSum = Math.max(nums[i], currentSum + nums[i]); maxSum = Math.max(maxSum, currentSum); } return maxSum; };11.2 算法思想
- 当前和为负则抛弃
- 当前和为正则保留
- 始终维护全局最大值
12. 三数之和
12.1 排序+双指针
var threeSum = function(nums) { const result = []; nums.sort((a, b) => a - b); const n = nums.length; for (let i = 0; i < n; i++) { if (i > 0 && nums[i] === nums[i - 1]) continue; let left = i + 1; let right = n - 1; while (left < right) { const sum = nums[i] + nums[left] + nums[right]; if (sum === 0) { result.push([nums[i], nums[left], nums[right]]); while (left < right && nums[left] === nums[left + 1]) left++; while (left < right && nums[right] === nums[right - 1]) right--; left++; right--; } else if (sum < 0) { left++; } else { right--; } } } return result; };12.2 去重技巧
- 排序：便于跳过重复元素
- 固定数去重：nums[i] === nums[i-1]时跳过
- 双指针去重：找到解后跳过相同left/right
13. 算法学习建议
- 分类练习：按算法类型（双指针、DFS、DP等）集中突破
- 手写实现：理解后自己实现，不要直接看答案
- 复杂度分析：养成分析时间/空间复杂度的习惯
- 反复练习：高频题目要多次练习达到熟练
在实际面试中，面试官不仅考察你能不能解出题目，更看重解题思路的清晰度和代码实现的规范性。建议在练习时注意代码风格，添加必要注释，展现良好的编程习惯。
