剑指Offer 48.最长不含重复字符的子字符串

#利用hash表的做法

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dic = {}
        tmp = res = 0
        for j in range(len(s)):
            i = dic.get(s[j],-1)
            dic[s[j]]=j
            tmp = tmp+1 if tmp 

 功能如下
 
 
利用线性方法 
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        res = tmp = i = 0
        for j in range(len(s)):
            i = j - 1
            while i >= 0 and s[i] != s[j]: i -= 1 # 线性查找 i
            tmp = tmp + 1 if tmp < j - i else j - i # dp[j - 1] -> dp[j]
            res = max(res, tmp) # max(dp[j - 1], dp[j])
        return res