LeetCode 第3题 无重复字符的最长子串（滑动窗口（双指针）+ HashSet）

一、核心算法思想采用滑动窗口双指针 HashSet时间复杂度 \(O(n)\)。定义窗口区间 \([i,rk]\)代表当前正在考察、无重复字符的连续子串i窗口左边界外层循环遍历rk窗口右边界只会向右移动不回退HashSet 集合occ实时保存当前窗口内部所有字符快速判断字符是否重复流程左边界i右移时将移出窗口的字符从集合删除在不重复前提下尽可能向右扩张右边界 rk每次扩张停止后计算窗口长度更新全局最长长度答案ans。区分概念子串必须连续子序列可以不连续。二、完整带注释代码class Solution { public int lengthOfLongestSubstring(String s) { // occ occurrence存储当前滑动窗口内的字符 SetCharacter occ new HashSet(); int n s.length(); int rk -1, ans 0; // rk右指针初始-1ansanswer保存最终结果 for(int i 0; i n; i){ if(i ! 0){ // 左边界右移把离开窗口的字符移除集合 occ.remove(s.charAt(i-1)); } // 右边界持续扩张下一个字符不越界、且窗口不存在该字符 while(rk 1 n !occ.contains(s.charAt(rk 1))){ occ.add(s.charAt(rk 1)); rk; } // 更新最长子串长度 ans Math.max(ans, rk - i 1); } return ans; } }三、实例运行推演输入s abcabcbbi (左边界)操作rk窗口\([i,rk]\)occ 集合当前窗口长度ans 最大值i0i0 无需 remove持续右扩 rk2[0,2]{a,b,c}3ans3i1删除 s [0] 字符 a右扩 rk3[1,3]{b,c,a}3ans3i2删除 s [1] 字符 b右扩 rk4[2,4]{c,a,b}3ans3i3删除 s [2] 字符 c右扩 rk5[3,5]{a,b,c}3ans3i4删除 s [3] 字符 a无法继续右扩5[4,5]{b,c}2ans3i5删除 s [4] 字符 b右扩 rk6[5,6]{c,b}2ans3i6删除 s [5] 字符 c无法继续右扩6[6,6]{b}1ans3最终返回 ans 3四、关键语法与内置方法、基础类型 包装类积累1. String 内置方法s.length()获取字符串长度必须带括号数组长度写法arr.length无括号s.charAt(index)String 内置方法根据下标获取对应字符⚠️方法名全小写charAt禁止写成CharAt2. Java 基础类型与对应包装类核心规则Java 中Set、List、Map等集合泛型不支持基础数据类型必须使用包装类。支持自动装箱、自动拆箱无需手动转换。基础类型基本类型对应包装类刷题场景示例byteByteSetByteshortShortMapShort,StringintIntegerSetInteger两数之和、最长连续序列高频longLongMapLong,IntegerfloatFloat极少用到doubleDouble极少用到booleanBooleanSetBooleancharCharacter本题SetCharacter3. HashSet 常用方法occ.add()字符加入集合occ.remove()删除指定字符occ.contains()判断字符是否存在集合内4. 通用工具方法Math.max(a,b)返回两个数字中较大的值用于更新最长长度五、高频易错点汇总大小写错误s.CharAt()❌ 正确s.charAt()缺少调用对象不能单独写charAt()必须写成s.charAt(下标)混淆length与length()字符串不要漏写括号逻辑误区不要一次性把全部字符放入集合集合occ只保存当前窗口内字符窗口扩张 → add窗口左移收缩 → remove保持集合与窗口内容同步rk 初始值设为-1窗口初始为空保证第一轮循环可以访问下标 0 的字符if(i ! 0)判断i0 是第一轮窗口左侧没有移出元素无需执行 remove六、变量名称释义刷题通用简写occoccurrence窗口内已经出现的字符集合rkright index滑动窗口右指针i滑动窗口左指针ansanswer保存最终答案最长无重复子串长度