3. 无重复字符的最长子串 - 力扣LeetCode题目给定一个字符串s请你找出其中不含有重复字符的最长子串的长度。思路找最长子串范围为i,j-1 第j个字符不在ij-1里就加入,在ij里i向右滑动需要的高频操作判断某个字符是否已经出现过查找加入新字符删除旧字符因此选择集合这个数据结构只存元素是否存在不关心顺序、不存重复值。class Solution(object): def lengthOfLongestSubstring(self, s): :type s: str :rtype: int #i,j-1 j不在ij-1里就加入,j向右滑动在就修改范围,i向右滑动 n len(s) i 0 j 1 if n 1 : return n res 0 seen set() while i n-1 and j n : if s[j] in seen : res max(len(seen),res) i 1 j i1 seen set() seen.add(s[i]) else : seen.add(s[j]) j 1 return max(len(seen),res)改进力扣通过但以上存在一个问题时间复杂度高。一旦遇到重复字符直接把左指针 1右指针重置到左 1集合清空重算。 时间复杂度最坏 O (n²)例如sabcdef全部无重复只会走一遍 O (n)但是saaaaa每次碰到重复都重置 jO (n²)。标准滑动窗口的做法不重置 j不清空 set遇到重复只移动左指针 i删除集合中 s [i]j 不回退注意此时最长子串的值不再是集合大小而是窗口大小class Solution(object): def lengthOfLongestSubstring(self, s): :type s: str :rtype: int n len(s) i 0 res 0 seen set() for j in range(n) : while s[j] in seen : seen.remove(s[i]) i 1 seen.add(s[j]) res max(res,j-i1) return res