【LeetCode 热题 100】3.无重复字符的最长子串：详解滑动窗口解法
📌 原题链接：Longest Substring Without Repeating Characters
📖 一、题目描述
给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。
示例：
输入: s = "abcabcbb"
输出: 3
解释: 最长不重复子串是 "abc"，长度为 3。
🧠 二、解题思路：滑动窗口 + 哈希集合
这是一道非常典型的滑动窗口问题。
✅ 为什么用滑动窗口？
如果我们使用暴力解法去尝试所有子串，时间复杂度会高达 O(n²)。
我们可以通过维护一个“不含重复字符的子串窗口”来动态处理：
- 使用两个指针
left和right表示当前窗口的左右边界。 - 用一个集合
set()来记录窗口内已经出现的字符。 - 如果出现重复，就移动左指针（收缩窗口）；否则右移右指针（扩展窗口）。
- 每次更新窗口时记录最大长度。
💻 三、Python 解法
class Solution:def lengthOfLongestSubstring(self, s: str) -> int:char_set = set()left = 0max_len = 0for right in range(len(s)):while s[right] in char_set:char_set.remove(s[left])left += 1char_set.add(s[right])max_len = max(max_len, right - left + 1)return max_len
🔍 四、关键语句逐行解释
class Solution:
定义一个类，这在 LeetCode 是默认要求的格式，系统会自动调用类中的方法。
def lengthOfLongestSubstring(self, s: str) -> int:
函数签名，表示接受一个字符串类型的参数 s，返回一个整数类型。
其中：
s: str是类型注解，说明参数是字符串-> int是返回类型注解，表示返回整数
char_set = set()
创建一个空的集合，用于记录当前窗口中的字符。
🧠 Python 中 set 的特点：
- 不重复：集合不能包含重复元素
- 无序：元素没有顺序
- 查找速度快：查找、添加、删除操作平均时间复杂度为 O(1)
while s[right] in char_set:
说明当前字符已经在窗口中了 → 出现重复
我们就不断从左边移除字符，直到窗口合法为止。
left += 1
left = left + 1 的简写，表示左指针向右移动一格（窗口缩小）
🧪 五、图解演示：以 “abcabcbb” 为例
- 初始窗口为空：
"" - 扩展右边界，加入
"a" → "ab" → "abc"，窗口合法。 - 遇到下一个
"a"，重复！此时不断移动左指针直到重复字符移出。 - 整个过程中记录窗口长度，得到最大值为
3。
你可以理解为“窗口在滑动”，但窗口内始终保持“无重复”的条件。
📈 六、复杂度分析
| 项目 | 分析 |
|---|---|
| 时间复杂度 | O(n)，每个字符最多进入和移除一次 |
| 空间复杂度 | O(min(n, m))，m 为字符集大小，如 ASCII 为 128 |
🧩 七、常见问题答疑
❓ self 是什么？
- 在类的方法中，第一个参数必须是
self，代表“这个对象自身”。 - 调用时系统自动传入，不需要你自己写。
❓ 为什么用 set() 而不是 list？
set查找是否包含某元素的效率是 O(1)，list是 O(n)- 用集合可以快速判断重复字符并删除，效率更高
❓ 如果我直接写一个函数不加 class 可以吗？
- 在 LeetCode 上不行，它要求你写在类里
- 在本地写是可以的，函数形式更自由
✅ 八、简洁版本（非类形式，供本地测试）
def length_of_longest_substring(s: str) -> int:char_set = set()left = 0max_len = 0for right in range(len(s)):while s[right] in char_set:char_set.remove(s[left])left += 1char_set.add(s[right])max_len = max(max_len, right - left + 1)return max_len
🏁 九、总结
| 技术点 | 说明 |
|---|---|
| 滑动窗口 | 用两个指针控制当前区间 |
集合 set() | 用于存储并快速查找重复字符 |
| 双指针 | 控制窗口动态扩展与收缩 |
| 类型注解 | 增强代码可读性，利于调试 |
✨ 十、后记
这道题是滑动窗口入门题，非常适合用来掌握双指针、集合操作、条件判断等核心编程思想。
🎯 掌握它后，你可以挑战更多类似问题，如：
- 最长不含重复字符的子串
- 最小覆盖子串
- 和为 K 的子数组
📌 如果觉得本篇博文对你有帮助，欢迎点赞 ⭐ 收藏 ❤️ 留言 📝！
我将持续更新 LeetCode 热题解析、算法思维图解与 Python 实战系列，帮助你高效刷题上岸！