LeetCode 第 3 题：无重复字符的最长子串（Python 代码）

题目 3. 无重复字符的最长子串 的描述如下：给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

子串 要求一定得是连续的，而 子序列 是可以不连续的。

这是一道没有多少知识点的题目，就是用 滑动窗口 的方式来写，算是一道挺简单的题目，但是想了我很久。我的方法和官方的题解是差不多的，但是写完之后看官方题解就感觉很好理解。先说一说我自己的写法，代码如下：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        if n < 2: return n  # 字符长度为 0 和 1 的时候直接返回 n
        ans = 1  # 子串最短也有 1
        i, j = 0, 0 # 左右指针
        cache = set(s[j])  # 哈希集合记录子串里的字符
        while j < n - 1 and i <= j:
            cache.add(s[j])
            if s[j+1] not in cache:  # 如果前面一个字符不存在
                j += 1  # 那么 j 往前一格把 s[j] 包含进去
                ans = max(ans, j - i + 1)  # 更新最长子串的长度
            else:  # 如果前面一个字符存在
                if i == j: j += 1  # 如果两个指针重合了，那么都要往前走
                cache.remove(s[i]) # 移除当前的左指针字符
                i += 1  # 左指针 i 往右一步
        return ans

滑动窗口（官方题解）

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        cache = set()  # 哈希集合，记录每个字符是否出现过
        n = len(s)
        # 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        rk, ans = -1, 0
        for i in range(n):
            if i != 0:
                cache.remove(s[i - 1])  # 左指针向右移动一格，移除一个字符
            while rk + 1 < n and s[rk + 1] not in cache:
                cache.add(s[rk + 1])  # 不断地移动右指针
                rk += 1
            # 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = max(ans, rk - i + 1)
        return ans

参考：LeetCode 官方题解