题名起得有点省但我一看就懂——又是LeetCode Hot 100系列。如果点进来的朋友已经刷到第3题说明正式进入“字符串双指针”这个经典战区了。这题作为滑动窗口的入门题几乎每一场算法面试都有可能出现不是因为它难而是因为它考察的东西非常基础且核心你怎么从暴力解一步步优化到O(n)你的窗口维护逻辑是不是够干净边界条件能不能一次写对。这篇文章不打算只贴个题解了事我会把这题从头到尾掰开揉碎讲清楚包括为什么滑动窗口有效、left指针到底怎么跳、HashMap和数组的选择逻辑、以及我刷题和面试里踩过的那些坑。先花十秒钟回顾一下题面给一个字符串 s找出其中不含有重复字符的最长子串的长度。比如 s abcabcbb答案是3因为abc和bca这些不重复子串长度最多就是3s bbbbb答案是1s pwwkew答案是3wke或kew。题目本身不难理解难点在于你怎么在最短的时间内写出无bug的代码并且能向面试官讲清楚每一步的思路。这篇博文适合所有正在刷LeetCode Hot 100的读者不管你刚入门还是想巩固滑动窗口都能从里面找到可以直接拿去用的经验。1. 先别急着写代码暴力解到滑动窗口的思路递进1.1 暴力解法为什么会超时我刚刷这题的时候第一反应其实是最朴素的枚举所有子串检查每个子串里有没有重复字符记录最大长度。听起来很直接但写出来一看复杂度O(n^2)个子串每个子串检查重复又要O(n)总共O(n^3)除非字符串长度很小否则基本就告别AC了。虽然LeetCode上这题数据量不大时暴力也能勉强过但面试官让你讲优化思路你总不能说“我暴力过了就行”。朴素的检查方式是用一个Set或者布尔数组遍历子串的每个字符如果发现已经存在就说明有重复。这里有个隐含的问题你在遍历每个子串时其实反复做了很多无意义的重复检测比如“abcdef”这个串abcde检查完无重复“abcdef”又要从头再检查一遍前五个字符明明已经检查过了。所以暴力法真正的痛点不是“枚举子串”这个想法错而是它没有把已经计算过的信息利用起来。这时候就该想到能不能让窗口滑动起来用一次遍历搞定所有子串的检查1.2 滑动窗口的核心直觉一个可变长度的窗口如果你把“无重复字符的最长子串”想象成一个窗口这个窗口从左往右滑动窗口里面装的字符永远保证不重复。那么你只需要维护这个窗口的左右边界不断扩展右边界一旦发现新字符和窗口内已有字符冲突就收缩左边界直到冲突解除。这样窗口的每一个位置都代表一个“以当前右边界结尾的无重复子串”你只要在这个过程中记录窗口的最大长度就可以了。听起来好像不难但这里有一个非常关键的思维转变题目问的是“最长子串”而滑动窗口每次维护的是“以当前字符结尾的最长无重复前缀”。这两者之间的关系是全局最长子串的右端点一定落在某个位置当你遍历到这个右端点时窗口的左边界会被推到正确的位置使得窗口正好覆盖这个最长子串。所以只要每次右移都记录窗口长度最终最大值一定不会漏掉。具体来说假设输入是abcabcbb右指针从0走到2时窗口内容分别是a、ab、abc都没重复ans跟着更新到3。右指针走到索引3的a时发现窗口里已经有a了这时候窗口左边就应该收缩到第一个a之后也就是从b开始。这时窗口变成bca长度还是3。后续的b同理窗口变成cab又遇到c时收缩到abc之后……整个过程一目了然窗口就像一条毛毛虫左边根据情况收缩右边一直往前爬。1.3 从“遇到重复就一点点挪”到“直接跳left”很多人第一次写滑动窗口会用while循环让left一格一格往右挪每挪一格就把字符从Set里删掉直到冲突解除。这样写本身没错逻辑上完全正确但有没有想过当右指针遇到重复字符“a”时left其实可以直接跳到上次“a”出现位置的下一个位置而不是一格一格试探这里就引出了滑动窗口的进阶优化用HashMap保存每个字符最近一次出现的下标遇到重复字符时left可以直接跳到map.get(s.charAt(right)) 1。为什么可以跳因为窗口内的所有字符都保证不重复当right位置的字符在窗口内重复出现时窗口内位于重复字符之前的所有字符都不可能再构成以当前right结尾的无重复子串了直接全部丢掉即可。跳过去省掉的不是一两次循环而是让整个过程从“可能抖动”变成“严格线性”。对于abcde f abcde这种长串如果每次重复都用while一点点挪left虽然总体仍是O(n)但常数开销会大不少而且代码容易写得啰嗦。HashMap跳法代码干净面试时也更好讲清楚。2. 核心细节哈希表、数组和窗口维护的边界2.1 HashMap存储的是什么字符上一次出现的位置先定义清楚我们用HashMapCharacter, Integer map来记录每个字符最近一次在字符串中出现的位置下标注意是最近一次不是第一次。当右指针right扫过一个字符c时先查map里有没有c如果有说明c在之前出现过。但这里必须判断一件事这个出现位置是否在当前窗口内如果left已经越过那个位置说明这个旧记录不在窗口内那它不构成任何限制left不需要动。这个细节特别容易写错。很多人第一次写会直接left map.get(c) 1不管这个旧位置在哪。但如果旧位置在left左边你把left往回跳窗口不但没收缩反而扩大了后面算出来的长度就是错的而且很难查。正确写法是left Math.max(left, map.get(c) 1)用max保证left只前进不后退。我当初就在这里吃过亏测试用例abba直接让我清醒。右指针扫到第二个a时map里记录的a位置是0但此时left因为之前那个b已经被推到了2如果不取max直接把left设成1窗口会往回扩答案就错了。这种错误靠肉眼很难发现因为小样例可能碰巧对长样例错了又不方便调试。所以记住这个max操作它是这题最关键的防呆设计。2.2 left的更新时机什么情况下才需要收缩再细抠一下收缩时机。右指针每次移动都要把当前字符c加进窗口。如果c之前出现过且出现位置在left和right之间那说明窗口内已经有c了这时需要把left移动到上次c出现位置 1。如果c之前没出现过或者出现位置在left左边那窗口不需要收缩直接扩展right就行。具体到代码里的写法有人习惯写if (map.containsKey(c)) { left Math.max(left, map.get(c) 1); }也有人不判断containsKey直接Integer pre map.put(c, right); if (pre ! null) { left Math.max(left, pre 1); }。两种都可以看个人习惯。我个人更推荐后者因为put方法返回旧值省了一次查找而且代码更紧凑。每次处理完窗口都要更新ansans Math.max(ans, right - left 1)。注意这个更新操作是在窗口调整完成之后做的因为你要记录的是“当前合法窗口”的长度。如果你在收缩前就更新可能记了一个包含重复字符的非法窗口长度虽然最终答案不一定错但逻辑上不够严谨。如果面试官较真这就是一个可以切入的扣分点。2.3 数组实现和HashMap实现谁更优其实这题的字符集是有限且已知的——ASCII字符最多128个扩展ASCII也就256个。所以完全可以用一个int[128]数组代替HashMap数组下标是字符的ASCII码存的值是该字符上次出现的位置。初始化全部为-1表示没出现过。用数组的好处是常数小没有哈希计算和装箱拆箱的开销LeetCode上古时期的测试数据差距可能不明显但在高负载场景或实际工程中数组方案确实更快。代码上也简单很多class Solution { public int lengthOfLongestSubstring(String s) { int[] lastIndex new int[128]; Arrays.fill(lastIndex, -1); int left 0; int ans 0; for (int right 0; right s.length(); right) { char c s.charAt(right); if (lastIndex[c] left) { left lastIndex[c] 1; } lastIndex[c] right; ans Math.max(ans, right - left 1); } return ans; } }这段代码里的if (lastIndex[c] left)其实就自动实现了“取max”逻辑如果旧位置已经小于left说明不在窗口内不需要收缩如果大于等于left说明在窗口内left跳过去。这个判断比HashMap写法的Math.max更直观一点也少一点歧义。如果你处理的是字符串且只包含小写字母可以只开int[26]然后减a不过为了通用性我还是习惯直接开128。数组方案唯一的限制是字符集范围。如果题目明确说明只包含英文字母那没问题。如果字符集是Unicode全量范围数组方案就不现实了必须用HashMap。不过LeetCode这题默认是ASCII数组方案可以放心用。面试时你可以主动提一句“这里字符集有限用数组替代哈希表可以省常数开销”面试官会对你另眼相看。3. 实操过程完整推导与代码实现3.1 手把手模拟一次完整遍历为了让你彻底理解这个算法我拿abcabcbb完整走一遍。初始时left0ans0所有lastIndex为-1。right0字符alastIndex[a]-1不小于left(0)所以left不动lastIndex[a]0ansmax(0, 0-01)1。right1字符blastIndex[b]-1left0lastIndex[b]1ans2。right2字符clastIndex[c]-1left0lastIndex[c]2ans3。right3字符alastIndex[a]0大于等于left(0)所以left011lastIndex[a]3ansmax(3, 3-11)3。right4字符blastIndex[b]1大于等于left(1)所以left112lastIndex[b]4ansmax(3, 4-21)3。right5字符clastIndex[c]2大于等于left(2)所以left213lastIndex[c]5ansmax(3, 5-31)3。right6字符blastIndex[b]4大于等于left(3)所以left415lastIndex[b]6ansmax(3, 6-51)2。right7字符blastIndex[b]6大于等于left(5)所以left617lastIndex[b]7ansmax(3, 7-71)1。最终答案3。你可以看到在right3和right4这两步left分别从0跳到1再跳到2窗口从左边界不断收缩而窗口长度始终被控制在最大不重复范围内。这个过程中ans只在窗口长度变大时更新缩小时不动所以它始终记录的是历史最大值。这里有个值得注意的现象在下标6和7窗口长度其实一直在缩小但ans保持3不变。这说明“最长子串”可能出现在遍历的中间阶段不一定在最后。所以你的代码必须每次遍历都更新ans不能等循环结束再统一计算。3.2 各语言实现参考我平时主力用Java但面试也写过Python和Go。核心逻辑一致这里给你三种参考实现。Python版本def length_of_longest_substring(s: str) - int: last_index {} left 0 ans 0 for right, c in enumerate(s): if c in last_index and last_index[c] left: left last_index[c] 1 last_index[c] right ans max(ans, right - left 1) return ans需要注意Python里if c in last_index在字典较大会有哈希开销但整体仍然是O(n)。如果不喜欢and last_index[c] left这种写法也可以拆开写。Go版本func lengthOfLongestSubstring(s string) int { lastIndex : make([]int, 128) for i : range lastIndex { lastIndex[i] -1 } left, ans : 0, 0 for right : 0; right len(s); right { c : s[right] if lastIndex[c] left { left lastIndex[c] 1 } lastIndex[c] right if right-left1 ans { ans right - left 1 } } return ans }Go的字符是按byte存的所以c : s[right]直接就是byte类型可以作为数组下标非常方便。如果你处理的是中文字符串那要用[]rune(s)转换后再处理否则会乱。3.3 复杂度分析为什么是O(n)这题的复杂度分析几乎必问。时间复杂度上left和right都只向右移动right每轮循环移动一步left虽然在窗口收缩时可能移动多步但总体移动次数不会超过n因为left最多从0走到n-1。所以两个指针的总移动次数是O(n)。哈希表或数组的读写都是O(1)整体时间复杂度就是O(n)。空间复杂度上数组方案是O(字符集大小)通常是O(128)即O(1)HashMap方案是O(min(m, n))m是字符集大小n是字符串长度因为map里最多存字符集大小个键值对。面试时建议主动说清楚这两者的区别而不是笼统说“O(n)空间”。我还遇到过面试官追问“如果字符串特别长比如几亿个字符但字符集只有26个字母用数组还是HashMap”答案显然是数组因为空间固定且减少哈希碰撞开销。这种追问其实在考察你对数据结构底层实现的理解而不是单纯背书。4. 常见问题与排查技巧实录4.1 为什么会把left往回跳这个坑我前面已经提过但值得单独再强调一次。典型错误写法是if (map.containsKey(c)) { left map.get(c) 1; }看起来逻辑没错遇到重复就跳到重复位置的下一个。但问题在于map里存的是“字符最后一次出现的位置”这个位置不一定是当前窗口内的位置。比如abba走到最后一步时right0 amap[a]0right1 bmap[b]1right2 bmap[b]1left2map[b]2right3 amap[a]0此时如果直接left011left从2变成1倒退了正确结果是left应该保持2不动因为旧a在索引0已经不在当前窗口[left2, right3]内了。你只要一倒退窗口就包含了已经丢掉的内容长度计算全乱。我之前帮学弟调代码时他一眼扫过去觉得没问题但一跑abba就挂了。这种问题非常隐蔽因为它不是你逻辑漏了而是你多做了操作。记住left只能前进不能后退。所有跳转都必须和当前left取最大值。4.2 边界条件空串、单字符、全重复字符写算法题最怕边界条件翻车。这题我整理几个必须测的用例测试用例期望输出说明0空串循环体不执行ans保持初始值0 1单个空格注意不是空串a1单个字符aaaa1全部相同字符窗口长度始终为1abca3重复在开头left需要跳abcabcbb3标准用例重复在中间abba2旧位置不在窗口内left不能回退tmmzuxt5重复在窗口内且后续会覆盖旧key最后一个用例我之前写测试时单独拿出来过。tmmzuxt正确输出是5mzuxt但很多人会在这里栽跟头。走一遍你就明白right0 t窗口tright1 m窗口tmright2 mleft跳到2窗口mright3 z窗口mzright4 u窗口mzuright5 x窗口mzuxright6 tlastIndex[t]0但这个位置小于left2所以left不动窗口变成mzuxt长度5。如果你在遇到t时因为map里有记录就直接left1那left就回退了窗口会错误地变成mzuxt之外的东西答案变成4甚至更小。4.3 多样例执行时为什么答案没重置如果你在LeetCode上连续跑多个测试用例发现异常或者自己写单测时多个用例串着跑很容易忘记重置left和ans。我在本地调试时踩过这种坑函数外的全局变量没清空第二次调用时left和ans还是上一次的值结果答案越算越离谱。解决办法很简单所有状态都定义在函数内部不要用类的成员变量存状态。LeetCode的Solution类虽然可以定义成员变量但最好保持无状态。另外如果你在循环里打印调试信息会发现数组方案里lastIndex[c] left这个判断也有讲究。有些写法是先更新lastIndex[c] right再判断那就会把当前字符算进去导致每次都触发收缩窗口长度永远是1。正确顺序是先判断旧位置是否在窗口内再更新lastIndex[c]为当前下标。这个顺序一定不能反。4.4 面试追问如果要求返回最长子串本身怎么办有的面试官不满足于返回长度会追问“现在不是返回长度是返回那个最长子串本身你怎么做”这时候你只需要在更新ans的同时记录对应的left和rightint bestLeft 0; int bestRight 0; for (int right 0; right s.length(); right) { char c s.charAt(right); if (lastIndex[c] left) { left lastIndex[c] 1; } lastIndex[c] right; if (right - left 1 ans) { ans right - left 1; bestLeft left; bestRight right; } } return s.substring(bestLeft, bestRight 1);注意这里更新bestLeft和bestRight的时机是在ans变大时而不是每次循环都记录。因为你只需要保存“当前最优解”的区间而不是所有区间。原理很直白ans变大的那一刻当前窗口就是新的最长子串候选ans没变大时新窗口不一定比旧窗口长没必要覆盖。这个思路同时适用于返回长度或返回子串本身面试时展现出这种“一题多解、灵活迁移”的能力会很加分。5. 从这题出发滑动窗口题型的通用套路5.1 窗口题的框架四步走刷完这题你会发现很多所谓“滑动窗口”的题都是同一个骨架只是细节上变了花样。我总结了一个通用框架后面遇到同类题直接套初始化left0ans初始化为0或一个极小值根据题目要求决定。右指针right从0开始遍历每步把s[right]加入窗口更新对应的数据结构哈希表、计数数组、Set等。检查窗口是否满足题目条件如果不满足收缩左边界left直到重新满足。更新答案ans然后right。第3步和第4步的先后顺序要看题目。比如这题你是先收缩再更新ans但有些题是“先更新ans再收缩”比如求“最短包含所有字符的子串”。关键在于你维护的窗口状态必须是合法状态然后在合法状态下记录答案。5.2 三个变体题检验你是真懂还是背答案你可以用这几道题来检验自己是不是真掌握滑动窗口第一道LeetCode 159至多包含两个不同字符的最长子串。这题让你找“只包含两种不同字符”的最长子串和本题很像只是约束从“无重复字符”变成“最多两个不同字符”。你需要维护窗口内不同字符的个数用一个HashMap记录每个字符在窗口内的数量当map.size() 2时收缩left同时减少对应字符的计数减到0就移除。第二道LeetCode 340至多有K个不同字符的最长子串。这是159的泛化版本把2改成K。写法和前面几乎一模一样唯一区别是判断条件是map.size() K。如果你能独立把这道题写对说明滑动窗口基础已经扎实了。第三道LeetCode 424替换后的最长重复字符。这题允许你最多替换K个任意字符让子串变成全相同字符。思路有点不一样你需要维护窗口内出现次数最多的字符个数maxCount窗口长度减去maxCount就是需要替换的字符数这个数不能超过K。如果超过K就收缩窗口。这道题比前两道多了一层“最大频次”的维护难度上了一个台阶但核心仍然是滑动窗口。这三道题做下来你对滑动窗口的理解会彻底不一样。以后看到字符串相关的“最长”、“最短”、“包含”、“覆盖”这些关键词脑子里会立刻浮现出left和right两根指针的样子。5.3 实际工程中的应用场景别觉得滑动窗口只是面试刷题用实际工程里它的应用非常广泛。比如日志分析里要统计一段时间窗口内的错误次数网络流量监控里要计算滑动时间窗内的平均带宽推荐系统里要基于用户最近N次行为做实时特征提取。这些场景本质上都是“维护一个可变的窗口并在窗口状态变化时做统计或决策”。理解了这题等于理解了这类处理逻辑的最小原型。我当年在一个数据同步工具里写过一段“最近5分钟内去重URL计数”的逻辑思路就是滑动窗口配合哈希表只是窗口的“滑动”是基于时间戳而不是数组下标。当时脑子里立刻浮现出这题只不过把right指针换成了当前时间把left指针换成了当前时间 - 5分钟。所以不要小看刷题基础算法思路一旦成为直觉工程上遇到类似问题就会有下手点。6. 实操心得从这题延伸到我的面试建议最后聊点我自己的经验。这道题在面试里的出现频率非常高如果面试官挑了这题大概率不是想考倒你而是想观察你“从暴力到优化”的思维过程。所以面试时不要上来就写最优解而是故意先提一句“这题最直接的想法是枚举所有子串但那样是O(n^3)。我们可以试试用滑动窗口把复杂度降到O(n)。”这一段话展示了你对复杂度的敏感度也给了面试官一个顺理成章的提问切入点。然后写代码的时候一边写一边说“这里用数组存上次出现的位置因为字符集有限”“left要用max保护不能回退”“每次循环都要更新ans”。这些话能让面试官知道你确实理解每个细节而不是背模板。我见过太多候选人代码写对了但说不清为什么left要取max这种“知其然不知其所以然”在面试官眼里等于没掌握。还有一个小建议刷完这题后当天就做一遍159和424趁热打铁形成肌肉记忆。同样的滑动窗口框架连续做三题比你隔三天再做一道效果要好得多。我在刷题社区里分享过这个经验不少人都反馈说“三连刷”之后对窗口题完全不怕了。如果你是在准备周赛或季度目标建议把这题标记为“必须手写不卡壳”的题目。因为它足够基础又包含了滑动窗口最核心的左指针收缩思想完全可以作为你复习窗口类问题的起手式。每次面试前我习惯快速过一遍这题代码就当热身保证手感在线。