摘要本文针对 LeetCode 中等题「无重复字符的最长子串」提供两种 Java 实现方案暴力枚举双层循环版本方便初学者理解题意滑动窗口双指针 HashSet版本是面试和提交的标准最优解。文章附带逐行代码讲解、样例推演、复杂度对比最后补充数组优化版本带你彻底掌握滑动窗口这类题。引言刷算法的时候滑动窗口属于非常高频的一类模板而这道题几乎是滑动窗口的入门必刷题目。很多同学刚上手会直接写出暴力双层循环逻辑很好懂但是有一定的局限性滑动窗口则用一次遍历就完成求解是我们需要重点掌握的思路。这里要先分清两个容易混淆的概念子串连续子序列不需要连续可以跳过字符选取。本题要求的是子串如果忽略“连续”这个关键点很容易写出完全错误的代码。题目描述给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。示例输入 s “abcabcbb”输出 3解释无重复最长子串为 “abc” 长度是 3。输入 s “bbbbb”输出 1输入 s “pwwkew”输出 3方法一暴力枚举双层循环思路枚举字符串中每一个下标 i 作为子串起点对于每一个起点再用 j 不断向后扩展使用 HashSet 保存当前子串已经出现过的字符一旦碰到已经存在的字符说明出现重复停止当前起点的遍历在遍历过程中持续更新最长长度。✅ 优点逻辑直白新手容易理解❌ 缺点时间复杂度 O(n^2)长用例容易超时仅适合学习Java 代码importjava.util.HashSet;classSolution{publicintlengthOfLongestSubstring(Strings){// 记录最长无重复子串长度intmaxLen0;// i子串起点for(inti0;is.length();i){// 每换一个起点新建集合清空记录HashSetCharactervisnewHashSet();// j子串终点从起点向后扩展for(intji;js.length();j){charchs.charAt(j);// 如果字符已经存在出现重复直接退出内层循环if(vis.contains(ch)){break;}vis.add(ch);// 更新最大长度maxLenMath.max(maxLen,j-i1);}}returnmaxLen;}}代码解析int maxLen 保存全局最长的合法子串长度。外层循环 i 遍历所有可能的子串起始位置。HashSet vis 放在外层循环内部保证每一个起点都独立统计不会复用上一轮的字符。内层循环 j 从起点向后延伸逐个取字符。如果 vis 里面已经存在当前字符立刻 break 连续子串一旦重复后面全部作废。j - i 1 计算当前 [i, j] 这段连续子串的长度。方法二滑动窗口双指针 HashSet推荐提交思路定义两个指针 left 、 right 标记窗口左右边界窗口 [left, right] 代表当前正在考察、没有重复字符的连续子串。right 不断向右扩张读取新字符如果新字符已经在窗口内就不断右移 left 把窗口左边的字符移除直到窗口不再存在重复字符窗口合法之后记录当前窗口长度更新最大值。✅ 时间复杂度O(n)每个字符最多被左右指针访问一次✅ 适合线上提交面试优先写这个版本Java 代码importjava.util.HashSet;classSolution{publicintlengthOfLongestSubstring(Strings){HashSetCharactersetnewHashSet();// 窗口左边界intleft0;intmaxLen0;// right 窗口右边界不断向右扩张for(intright0;rights.length();right){charcs.charAt(right);// 如果当前字符已经在窗口持续收缩左边界while(set.contains(c)){set.remove(s.charAt(left));left;}// 将新字符加入窗口set.add(c);// 更新最长长度maxLenMath.max(maxLen,right-left1);}returnmaxLen;}}代码解析HashSet 存储当前窗口里面所有字符用来快速查重。right 遍历整个字符串作为窗口右边界负责扩张。while(set.contains©) 这里必须使用 while而不是 if。重复字符可能距离左边界很远需要一直收缩窗口直到没有重复。left 收缩窗口把左边的字符从集合中移除。right - left 1 当前合法窗口的长度对比更新最长值。⚠️ 易错点如果这里把 while 改成 if只能挪动一次左指针无法清除全部重复会导致答案错误。两种方案对比方案 时间复杂度 空间复杂度 特点暴力枚举 好理解长字符串超时适合入门学习滑动窗口 效率高面试、提交首选拓展ASCII 数组优化版本如果追求极致速度可以使用 ASCII 数组替代 HashSet。字符的 ASCII 范围有限用数组标记字符最后出现的下标查询速度更快也是很多面试官更喜欢的写法。classSolution{publicintlengthOfLongestSubstring(Strings){// ASCII 一共 128int[]arrnewint[128];intleft0;intmaxLen0;for(intright0;rights.length();right){charcs.charAt(right);leftMath.max(left,arr[c]);maxLenMath.max(maxLen,right-left1);arr[c]right1;}returnmaxLen;}}✍️ 刷题心得刚开始刷这道题第一反应很容易就是双层循环把所有子串全部枚举一遍这种思路最贴合题意但是算法题里暴力解法大多只能用来验证思路很难通过全部测试用例。滑动窗口本质就是维持一个满足条件的区间右指针不断扩大区间当区间不再满足条件的时候移动左指针收缩区间让区间重新合法。很多 “最长连续子数组 / 子串” 的题目都可以套用这套模板比如最小覆盖子串和为 K 的子数组无重复字符的最长子串刷题的时候不要只背代码要想清楚两件事窗口需要满足什么条件什么时候扩大窗口、什么时候收缩窗口把这个模板吃透以后遇到同类题目就可以快速迁移思路。总结暴力法适合刚开始理解题意看懂“枚举所有子串”的思想滑动窗口是这道题的标准解法也是面试高频考点滑动窗口核心思想窗口始终维持合法右扩左缩适合解决很多“最长连续子串”类题目。
摘要本文针对 LeetCode 中等题「无重复字符的最长子串」提供两种 Java 实现方案暴力枚举双层循环版本方便初学者理解题意滑动窗口双指针 HashSet版本是面试和提交的标准最优解。文章附带逐行代码讲解、样例推演、复杂度对比最后补充数组优化版本带你彻底掌握滑动窗口这类题。引言刷算法的时候滑动窗口属于非常高频的一类模板而这道题几乎是滑动窗口的入门必刷题目。很多同学刚上手会直接写出暴力双层循环逻辑很好懂但是有一定的局限性滑动窗口则用一次遍历就完成求解是我们需要重点掌握的思路。这里要先分清两个容易混淆的概念子串连续子序列不需要连续可以跳过字符选取。本题要求的是子串如果忽略“连续”这个关键点很容易写出完全错误的代码。题目描述给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。示例输入 s “abcabcbb”输出 3解释无重复最长子串为 “abc” 长度是 3。输入 s “bbbbb”输出 1输入 s “pwwkew”输出 3方法一暴力枚举双层循环思路枚举字符串中每一个下标 i 作为子串起点对于每一个起点再用 j 不断向后扩展使用 HashSet 保存当前子串已经出现过的字符一旦碰到已经存在的字符说明出现重复停止当前起点的遍历在遍历过程中持续更新最长长度。✅ 优点逻辑直白新手容易理解❌ 缺点时间复杂度 O(n^2)长用例容易超时仅适合学习Java 代码importjava.util.HashSet;classSolution{publicintlengthOfLongestSubstring(Strings){// 记录最长无重复子串长度intmaxLen0;// i子串起点for(inti0;is.length();i){// 每换一个起点新建集合清空记录HashSetCharactervisnewHashSet();// j子串终点从起点向后扩展for(intji;js.length();j){charchs.charAt(j);// 如果字符已经存在出现重复直接退出内层循环if(vis.contains(ch)){break;}vis.add(ch);// 更新最大长度maxLenMath.max(maxLen,j-i1);}}returnmaxLen;}}代码解析int maxLen 保存全局最长的合法子串长度。外层循环 i 遍历所有可能的子串起始位置。HashSet vis 放在外层循环内部保证每一个起点都独立统计不会复用上一轮的字符。内层循环 j 从起点向后延伸逐个取字符。如果 vis 里面已经存在当前字符立刻 break 连续子串一旦重复后面全部作废。j - i 1 计算当前 [i, j] 这段连续子串的长度。方法二滑动窗口双指针 HashSet推荐提交思路定义两个指针 left 、 right 标记窗口左右边界窗口 [left, right] 代表当前正在考察、没有重复字符的连续子串。right 不断向右扩张读取新字符如果新字符已经在窗口内就不断右移 left 把窗口左边的字符移除直到窗口不再存在重复字符窗口合法之后记录当前窗口长度更新最大值。✅ 时间复杂度O(n)每个字符最多被左右指针访问一次✅ 适合线上提交面试优先写这个版本Java 代码importjava.util.HashSet;classSolution{publicintlengthOfLongestSubstring(Strings){HashSetCharactersetnewHashSet();// 窗口左边界intleft0;intmaxLen0;// right 窗口右边界不断向右扩张for(intright0;rights.length();right){charcs.charAt(right);// 如果当前字符已经在窗口持续收缩左边界while(set.contains(c)){set.remove(s.charAt(left));left;}// 将新字符加入窗口set.add(c);// 更新最长长度maxLenMath.max(maxLen,right-left1);}returnmaxLen;}}代码解析HashSet 存储当前窗口里面所有字符用来快速查重。right 遍历整个字符串作为窗口右边界负责扩张。while(set.contains©) 这里必须使用 while而不是 if。重复字符可能距离左边界很远需要一直收缩窗口直到没有重复。left 收缩窗口把左边的字符从集合中移除。right - left 1 当前合法窗口的长度对比更新最长值。⚠️ 易错点如果这里把 while 改成 if只能挪动一次左指针无法清除全部重复会导致答案错误。两种方案对比方案 时间复杂度 空间复杂度 特点暴力枚举 好理解长字符串超时适合入门学习滑动窗口 效率高面试、提交首选拓展ASCII 数组优化版本如果追求极致速度可以使用 ASCII 数组替代 HashSet。字符的 ASCII 范围有限用数组标记字符最后出现的下标查询速度更快也是很多面试官更喜欢的写法。classSolution{publicintlengthOfLongestSubstring(Strings){// ASCII 一共 128int[]arrnewint[128];intleft0;intmaxLen0;for(intright0;rights.length();right){charcs.charAt(right);leftMath.max(left,arr[c]);maxLenMath.max(maxLen,right-left1);arr[c]right1;}returnmaxLen;}}✍️ 刷题心得刚开始刷这道题第一反应很容易就是双层循环把所有子串全部枚举一遍这种思路最贴合题意但是算法题里暴力解法大多只能用来验证思路很难通过全部测试用例。滑动窗口本质就是维持一个满足条件的区间右指针不断扩大区间当区间不再满足条件的时候移动左指针收缩区间让区间重新合法。很多 “最长连续子数组 / 子串” 的题目都可以套用这套模板比如最小覆盖子串和为 K 的子数组无重复字符的最长子串刷题的时候不要只背代码要想清楚两件事窗口需要满足什么条件什么时候扩大窗口、什么时候收缩窗口把这个模板吃透以后遇到同类题目就可以快速迁移思路。总结暴力法适合刚开始理解题意看懂“枚举所有子串”的思想滑动窗口是这道题的标准解法也是面试高频考点滑动窗口核心思想窗口始终维持合法右扩左缩适合解决很多“最长连续子串”类题目。
