读完本文你将了解最长无重复子串的核心解法 | 暴力→滑动窗口的优化演进 | 面试官想看到的边界处理 题目原题给定一个字符串 s找出其中不含有重复字符的最长子串的长度。项目说明输入s “abcabcbb”输出3解释“abc” 长度 3是无重复字符的最长子串约束0 ≤ s.length ≤ 5×10⁴s 由英文字母、数字、符号和空格组成 先问一个问题ChatGPT 第一次写这道题会怎么写不是哈希表不是滑动窗口——先写一个双层循环。AI 的第一版代码暴露了最自然的思维方式也恰恰是我们要优化的起点。 第一版AI 的朴素解法暴力枚举deflength_of_longest_substring(s:str)-int:max_len0foriinrange(len(s)):seenset()forjinrange(i,len(s)):ifs[j]inseen:breakseen.add(s[j])max_lenmax(max_len,j-i1)returnmax_len外层遍历每个起始位置内层从当前位置往后找遇到重复字符停下来记录当前最大长度。复杂度时间 O(n²) 空间 O(min(m, n))问题每次外层 i 递增内层 j 又从头扫——大量重复计算。 AI 的自我优化问 AI “能不能更快”它的思考链第 1 次内层很多工作是重复的——j 遇到重复字符时i 没必要只1 再从头扫可以跳到重复位置的下一个第 2 次用哈希表记录字符上次出现的位置i 直接跳跃不需要内层循环重新构建 set最终版双指针滑动窗口左指针只在必要时移动右指针一直往前走暴力枚举O(n²)滑动窗口O(2n)哈希优化滑动窗口O(n)最终版代码deflength_of_longest_substring(s:str)-int:char_index{}# 字符 - 最近出现位置left0max_len0forright,chinenumerate(s):ifchinchar_indexandchar_index[ch]left:# 遇到重复字符左指针跳到重复位置的下一个leftchar_index[ch]1char_index[ch]right max_lenmax(max_len,right-left1)returnmax_len复杂度时间 O(n)空间 O(min(m, n))——每个字符最多被访问两次核心洞察右指针永不回退左指针只在必要时跳跃。☕ Java 实现publicintlengthOfLongestSubstring(Strings){MapCharacter,IntegercharIndexnewHashMap();intleft0,maxLen0;for(intright0;rights.length();right){charchs.charAt(right);if(charIndex.containsKey(ch)charIndex.get(ch)left){leftcharIndex.get(ch)1;}charIndex.put(ch,right);maxLenMath.max(maxLen,right-left1);}returnmaxLen;}CSDN 第一大用户群体是 Java 开发者。两版代码摆在一起对比比讲十句话都有用。 算法模式拆解这题属于滑动窗口Sliding Window模式。什么时候用滑动窗口问题涉及连续子数组/子串需要在 O(n) 时间内处理窗口的扩展和收缩有明确的条件判断滑动窗口模板defsliding_window(s):left0result0window{}# 或 set/counterforright,chinenumerate(s):# 扩展窗口window[ch]window.get(ch,0)1# 收缩窗口条件不满足时while需要收缩的条件:window[s[left]]-1left1# 更新结果resultmax(result,right-left1)returnresult同类问题至多包含 K 个不同字符的最长子串最小覆盖子串无重复字符的最长子串本题字符串的排列️ 真实产品场景你在用 Slack 看团队消息。频道里消息在滚动你关注的是最近的消息流中有没有重复的发送者。Slack 的未读消息摘要功能需要从最近的 N 条消息中提取不重复的发送者列表——这就是滑动窗口。是左指针跳到第一个 Alice 之后否继续扩展消息流[Alice, Bob, Alice, Charlie, Bob, Dave]窗口从 Alice 开始遇到重复 Alice?窗口: [Bob, Alice, Charlie, Bob, Dave]继续右移遇到重复 Bob?左指针跳跃窗口: [Alice, Charlie, Bob, Dave]不只是 Slack——任何需要处理连续数据流中的不重复模式的场景网络流量分析检测最近的数据包中是否有重复源地址日志去重实时日志流中提取最近 N 条唯一错误码股票交易最近 K 笔交易中不重复的股票代码✅ 面试官的点评答到什么算通过级别标准基础暴力解写出 O(n²) 解法能分析复杂度良好滑动窗口写出 O(2n) 版本解释清楚左右指针的作用优秀哈希优化写出 O(n) 版本左指针直接跳跃处理边界正确加分能扩展到「至多 K 个不同字符」的变体常见坑忘了char_index[ch] left——字符虽然出现过但已经不在当前窗口内空字符串 s “”——返回 0 不是 None全是相同字符 “bbbbb”——正确返回 1加分细节字符集大小有限ASCII 128 个可以用数组代替哈希表进一步优化空间主动问面试官字符串的字符集范围是多少 同类题推荐题目难度一句话思路至多包含 K 个不同字符的最长子串Medium窗口内维护不同字符计数超过 K 时左指针收缩最小覆盖子串Hard先扩展找到所有目标字符再收缩找最小字符串的排列Medium固定窗口大小目标串长度滑动比较字符计数来源说明✅ 已验证LeetCode 官方题解 Python/Java 实测✅ 已验证产品场景源自 Slack、网络流量分析等真实用例