给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if not s:return 0 left = 0 lookup = set() n = len(s) max_len = 0 cur_len = 0 for i in range(n): cur_len += 1 #如果新的字符在当前窗口内。则窗口跳过当前的窗口,重新开始获得新的窗口。i=1,s[i]=k;s[i-1]=k=s[0] while s[i] in lookup:#为什么这里要用while?因为只remove了最左边的字符,还需要进行循环remove lookup.remove(s[left]) left += 1 cur_len -= 1 #如果新的字符不在当前窗口内: if cur_len > max_len: max_len = cur_len #无论如何都会向后添加窗口后的第一个元素 lookup.add(s[i]) return max_len
整体的思路也就是使用滑动窗口法,首先窗逐渐扩大,扩大到直到遇到了重复的字串后,则移动left指针,每次left指针向右移动一次,则将当前窗口left所指的字符remove掉,同时记录当前字符串长度的cur_len减去1,直到当前窗口中没有任何重复的字符,如字符串:
kbakiop当中
第一个窗口为kba,接着遇到新的k后,则变成了kbak,然后在while循环当中对k进行排除,最左边的k正好是左边的left指针这样新的窗口就变成了bak,然后后面的iop因为都不在窗口当中,因此最后的窗口包含的字符为:bakiop,长度则为6。
标签:子串,字符,窗口,cur,python,len,字串,leetcode,left From: https://www.cnblogs.com/geeksongs/p/17010530.html