最长无重复子串
无重复字符的最长子串
这个问题两个思路，要么进行遍历暴力破解，要么进行滑动窗口（巧妙），下面先看一下暴力解法：
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: s_count = len(s) max_list = [] if s_count == 0: return 0 else: # 两层的遍历 for i in range(s_count): tmp = s[i] max_list.append(tmp) for j in range(i+1, s_count): tmp += s[j] max_list.append(tmp) # 然后用set 判断子串是否有重复 return max([len(i) for i in max_list if len(set(list(i))) == len(i)])
这个时间复杂度是N方，下面看一下滑动窗口的解法，我来一个left和right，然后用right遍历，如果有重复子串，我就删除left，知道没有重复为止，这个思路太可以了。
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: left = 0 s_len = len(s) max_count = 0 # 用set 来记录最长无重复子串 max_set = set() # right 遍历 s for right in range(s_len): # 如果在set 中 我就删除左边的 直到没有重复为止 while s[right] in max_set: max_set.remove(s[left]) left += 1 max_set.add(s[right]) max_count = max(max_count, right - left + 1) return max_count
滑动窗口的时间复杂度是O（N），提高不少。