滑动窗口

题目1:给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。

 

      class Solution:
          def lengthOfLongestSubstring(self, s: str) -> int:
              if not s:return 0
              left = 0
              lookup = set()
              n = len(s)
              max_len = 0
              cur_len = 0
              for i in range(n):
                  cur_len += 1
                  while s[i] in lookup:
                      lookup.remove(s[left])
                      left += 1
                      cur_len -= 1
                  if cur_len > max_len:max_len = cur_len
                  lookup.add(s[i])
              return max_len

题目2:给你两个字符串 s1 和 s2 ,写一个函数来判断 s2 是否包含 s1 的排列。如果是,返回 true ;否则,返回 false 。换句话说,s1 的排列之一是 s2 的 子串 。

 

        ```
          class Solution:
              #s2中存在一个区间,与s1元素个数相同,且相等
              def checkInclusion(self, s1: str, s2: str) -> bool:
                  need, window = {}, {}
                  for c in s1:
                      need[c] = need.setdefault(c, 0) + 1
                  left, right = 0, 0
                  valid = 0
                  while right < len(s2):
                      c = s2[right]
                      right += 1
                      if c in need:
                          window[c] = window.setdefault(c, 0) + 1
                          if window[c] == need[c]:
                              valid += 1
                      while right - left >= len(s1):
                          if valid == len(need):
                              return True
                          d = s2[left]
                          left += 1
                          if d in need:
                              if window[d] == need[d]:
                                  valid -= 1
                              window[d] -= 1
                  return False
          ```