与子同程
Leetcode Hot 1002 分钟
5 次阅读

无重复字符的最长子串

本文详细解析 LeetCode 第3题“无重复字符的最长子串”，通过滑动窗口算法，提供两种 Python 解法，并分析思路与优化。

LeetcodePython滑动窗口哈希表
无重复字符的最长子串 封面图

阅读要点

  • 滑动窗口算法解决无重复字符子串问题
  • 两种 Python 实现：固定左指针 vs 双指针同时滑动
  • 使用 set 维护窗口内字符，实现 O(1) 查重

​题目

3. 无重复字符的最长子串 - 力扣（LeetCode）

解法

思路

采用滑动窗口来探求满足条件的最长子串，右指针先向右滑动，直至不满足条件，左指针再向右滑动，直至满足条件。

答案

题解的解法，左指针遍历每一个元素，右指针滑动，时间略长

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        res = 0
        for i in range(len(s)):
            s_set = set()
            r = i
            while r < len(s) and s[r] not in s_set:
                s_set.add(s[r])
                r += 1
            res = max(res, r - i )
 
        return res

思路中的解法，左右指针同时滑动

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        res = 0
 
        i, j = 0, 0
        s_set = set()
        while i <= j and j < len(s):
 
            while j < len(s) and s[j] not in s_set:
                s_set.add(s[j])
                res = max(res, j - i + 1)
                j += 1
            # 此时s[j]在之前出现过
            while i <= j and j < len(s) and s[j] in s_set:
                s_set.remove(s[i])
                i += 1
 
        return res