算法 面试题
共 22 道 算法 面试题。答案默认折叠，便于先自行作答。 1. 不重复最大子串 难度：2 · 类型：QA 给定一个字符串，请实现一个函数来找到其中的不重复最大子串。例如，对于字符串"abcabcbb"，不重复最大子串是"abc"，长度为3。 请写出实现该功能的代码，并说明其时间复杂度。 考虑到性能优化，你认为还有哪些改进空间？请提出优化思路并实现优化后的代码。 题目要点 滑动窗口 是解决最长不重复子串问题的核心思想。 Set 方法简单直观，但每遇到重复字符可能多次移动左指针。 Map 优化通过记录字符索引，直接跳过重复区域，减少不必要操作。 时间复杂度 O(n)，空间复杂度 O(Σ)。 参考答案 一、滑动窗口实现 function lengthOfLongestSubstring(s) { let set = new Set(); let left = 0, maxLen = 0; for (let right = 0; right < s.length; right++) { while (set.has(s[right])) { set.delete(s[left]); left++; } set.add(s[right]); maxLen = Math.max(maxLen, right - left + 1); } return maxLen; } // 测试 console.log(lengthOfLongestSubstring("abcabcbb")); // 输出 3 思路 使用 滑动窗口 [left, right] 遍历字符串。 用 Set 存储当前窗口内字符。 当遇到重复字符时，移动左指针，直到窗口内无重复字符。 每次窗口扩大时更新最大长度。 时间复杂度 每个字符 最多进出窗口一次 → O(n) 空间复杂度：O(min(n, Σ))，Σ 是字符集大小。 二、性能优化 上面方法每遇到重复字符，需要 逐个删除左边字符。可以进一步优化为 直接跳过重复字符的索引，使用 Map 存储字符上次出现的索引。 ...