【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 = 0
        max_len = 0

        for right in range(len(s)):
            while s[right] in char_set:
                char_set.remove(s[left])
                left += 1
            char_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” 为例

1. 初始窗口为空：""
2. 扩展右边界，加入 "a" → "ab" → "abc"，窗口合法。
3. 遇到下一个 "a"，重复！此时不断移动左指针直到重复字符移出。
4. 整个过程中记录窗口长度，得到最大值为 3。

你可以理解为“窗口在滑动”，但窗口内始终保持“无重复”的条件。

📈 六、复杂度分析

🧩 七、常见问题答疑

❓ self 是什么？

• 在类的方法中，第一个参数必须是 self，代表“这个对象自身”。
• 调用时系统自动传入，不需要你自己写。

❓ 为什么用 set() 而不是 list？

• set 查找是否包含某元素的效率是 O(1)，list 是 O(n)
• 用集合可以快速判断重复字符并删除，效率更高

❓ 如果我直接写一个函数不加 class 可以吗？

• 在 LeetCode 上不行，它要求你写在类里
• 在本地写是可以的，函数形式更自由

✅ 八、简洁版本（非类形式，供本地测试）

def length_of_longest_substring(s: str) -> int:
    char_set = set()
    left = 0
    max_len = 0

    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)

    return max_len

🏁 九、总结

✨ 十、后记

这道题是滑动窗口入门题，非常适合用来掌握双指针、集合操作、条件判断等核心编程思想。

🎯 掌握它后，你可以挑战更多类似问题，如：

• 最长不含重复字符的子串
• 最小覆盖子串
• 和为 K 的子数组