当前位置 博文首页 > 明圣的博客:3. 无重复字符的最长子串

    明圣的博客:3. 无重复字符的最长子串

    作者:[db:作者] 时间:2021-08-07 15:42

    先给出一个错误答案,这个答案错在解决不了abcb型的测试用例

    class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
    if not s:return 0
    left = 0#左指针
    lookup = set()
    n = len(s)
    maxlen = 0
    curlen = 0#滑动窗口
    for i in range(n):
    curlen += 1
    while s[i] in lookup:
    lookup.remove(s[left])
    left += 1
    curlen -= 1
    if curlen > maxlen:maxlen = curlen
    lookup.add(s[i])
    return maxlen

    正确答案,用的滑动窗口的概念,就是一个列表

    class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
    if not s:return 0
    left = 0#左指针
    lookup = set()
    n = len(s)
    maxlen = 0
    curlen = 0#滑动窗口
    for i in range(n):
    curlen += 1
    while s[i] in lookup:
    lookup.remove(s[left])
    left += 1
    curlen -= 1
    if curlen > maxlen:maxlen = curlen
    lookup.add(s[i])
    return maxlen

    笔记:
    1、不要忘记考虑空字符串
    2、基于滑动窗口的特性,最后(c,b,b)是3,虽然有重复,但是也不会超过最大长度子串

    cs