题目

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
例如：

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
复制

代码

暴力解法-用例通过986/987

因为是求最长的无重复子串的长度，故长度递减循环，而索引递增循环。通过set去重前后的字符串长度是否相同判断当前子串是否为无重复字符的子串，如果是则输出长度
最终超时。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n=len(s)
        S=[x for x in s]
        if s=='':
            return 0
        else:
            for length in range(n,0,-1):
                for index in range(0,n-length+1):
                    print(index)
                    a=S[index:index+length]
                    b=set(a)
                    if len(a)==len(b):
                        return length
                    
复制

双指针

从左往右遍历字符串，用字典记录{字符串：位置}的键值对。
右指针right始终为当前遍历位置，左指针的初值为0，根据情况更新。
若当遍历的字符在字典中有记录，则当前左右指针为起始位置的子串的无重复性可能会被破坏，因此查找上一次这个重复字符出现的位置。
如果这个位置k在当前子串内部，则更新左指针为k+1，那么当前子串保持了无重复字符的性质。
如果位置k在当前子串外部，保持左指针位置不变，当前子串仍然是一个无重复子串。
这样就遍历过了所有的无重复子串，不断更新长度max_length则可得到最大长度。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 处理空串
        if s=='':
            return 0
        
        L={} # 记录字符:位置
        left=0 # 左指针
        max_length=1 # 最长无重复字符子串的长度
        for i in range(len(s)):
            right=i # 右指针
            if s[i] not in L:
                L[s[i]]=i
            else:
                left=max(L[s[i]]+1,left) #更新左指针
                L[s[i]]=i # 更新字符位置

            # 更新无重复字符子串的长度
            tmp=right-left+1
            if tmp>max_length:
                max_length=tmp
            # print(left,right)    
        return max_length
                
                


         

复制