当前位置：首页 > news >正文

Leetcode刷题记录19——无重复字符的最长子串

news 2025/4/27 14:49:41

题源：https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-100-liked

题目描述：
在这里插入图片描述
思路一：
通过两个指针，第一个指针指向字串的开头，第二个指针向后找，直到找到重复的字符或者到达字符的末尾，第二个指针每向后移动一位，当前的子串长度加一，然后与最大长度作比较，留下更大的那个作为最长子串长度。
代码如下：

class Solution(object):def lengthOfLongestSubstring(self, s):""":type s: str:rtype: int"""max_len = 0     # 最长子串长度cur_max_len = 0 # 当前找到的最长子串长度cur_set = set()for i in range(len(s)):j = icur_max_len = 0cur_set = set()while j < len(s) and s[j] not in cur_set:cur_set.add(s[j])j += 1cur_max_len += 1max_len = max(max_len, cur_max_len)return max_len

执行时间如下：
在这里插入图片描述
思路二：
思路二其实是对思路一的优化，我们可以看到思路一中这一段代码：

cur_set = set()while j < len(s) and s[j] not in cur_set:cur_set.add(s[j])j += 1cur_max_len += 1max_len = max(max_len, cur_max_len)

当我们找到那个重复的字母时，不需要把右边的指针拉回来重新遍历，因为此时已经可以确定左右指针之间的最长无重复字串长度，无需再进行遍历，更快的做法是向前移动左边的指针，直到找到不重复的字串，将此时的左边指针作为字串开头，移动右边指针继续思路一的遍历即可。
代码实现如下：

class Solution(object):def lengthOfLongestSubstring(self, s):""":type s: str:rtype: int"""max_len = 0cur_max_len = 0cur_set = set()left = right = 0while left <= right and right < len(s):if s[right] not in cur_set:cur_set.add(s[right])right += 1cur_max_len += 1max_len = max(max_len, cur_max_len)else:cur_set.discard(s[left])left += 1cur_max_len -= 1return max_len