滑动窗口

方法一滑动窗口

定义两个指针，右指针负责扩充窗口，左指针负责收缩窗口。当扩张的过程中遇到了重复，就需要收缩到直到把重复的字符移除出去。

参考代码

  1. class Solution:
  2.     def lengthOfLongestSubstring(self, s: str) -> int:
  3.         l = len(s)
  4.         left,right,ans = 0,0,0
  5.         win = set()
  6.         while right < l:
  7.             if s[right] not in win:
  8.                 win.add(s[right])
  9.                 ans = max(ans,right - left + 1)
  10.             else:
  11.                 while s[left] != s[right]:
  12.                     win.remove(s[left])
  13.                     left += 1
  14.                 left += 1
  15.             right += 1
  16.         return ans

复杂度分析

时间复杂度 O(n) n为数组长度，左指针和又指针会分别遍历一遍
空间复杂度 O(m) m为字符集长度