3. 无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
思路
- 确定求解顺序: 要求最长子串, 我们需要从更短的字符串开始逐步求解, 我们可以从左到右来逐步找到无重复的子串, 同时记录长度最长的子串长度
- 如何从左到右, 不遗漏也不重复的找出所有子串: 需要用到一个技巧--滑动窗口
- 滑动窗口:
- 我们从左至右遍历字符串s, 用窗口记录当前的无重复字符的最长子串
- 如果当前字符没有在窗口中, 则将其添加至窗口中
- 如果当前字符串在窗口中, 我们移动窗口最左侧,直到当前字符不在窗口中
- 每次移动索引都获取窗口长度, 尝试记录最大长度
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
lst = [] # 滑动窗口
left = 0 # 用户滑动窗口最左侧的索引, 用于滑动窗口
max_len = 0 # 记录最大的字符串长度
# 遍历字符串
for char in s:
# 如果滑动窗口有当前字符(即有重复字符), 左索引向右移动,直到没有当前字符
while char in lst[left:]:
left+=1
lst.append(char) # 把每个当前字符都加到滑动窗口中
if len(lst)-left > max_len: max_len=len(lst)-left # 记录最大长度
return max_len # 返回最大长度
- 此方法性能不是最优, 但容易理解
如果对你有帮助, 点个喜欢并关注我, 也可以评论, 谢谢, 我每天都会做一个题!
