实现思路

方法:双指针 + sliding window

  • 定义两个指针 start 和 end 得到 sliding window
  • start 初始为 0,用 end 线性遍历每个字符,用 recod 记录下每个字母最新出现的下标

两种情况:一种是新字符没有在 record 中出现过,表示没有重复,一种是新字符 char 在 record 中
出现过,说明 start 需要更新,取 start 和 record[char]+1 中的最大值作为新的 start。

**需要注意的是:两种情况都要对 record 进行更新,因为是新字符没在 record 出现过的时候需要添加
到 record 中,而对于出现过的情况,也需要把 record 中对应的 value 值更新为新的**

示例代码

class Solution:
   def lengthOfLongestSubstring(self, s: str) -> int:
       record = {}
       start,res = 0,0
          for end in range(len(s)):
          if s[end] in record:
            start = max(start, record[s[end]] + 1)
            record[s[end]] = end
            res = max(res, end - start + 1)
       return res

时间复杂度:O(n)
空间复杂度:O(1)