第 6 天

滑动窗口

---

3. 无重复字符的最长子串

给定字符串s，请找出不含重复字符的。最长子串的长度。

示例1:

输入: s = "abcabcbb" 输出: 3  解释: 因为无重复字符的最长子串是 "abc"，所以它的长度是 3。 

示例 2:

输入: s = "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 'b所以它的长度是 1。 

示例 3:

输入: s = "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是"wke"，所以它的长度是 3.请注意，你的答案一定是 子串 的长度，"pwke"是一个子序列，不是子串。

class Solution:     def lengthOfLongestSubstring(self, s: str) -> int:         list1 = []         maxnum = 0         for i in s:             if i not in list1:                 list1.append(i)             else:                 for j in range(len(list1)):                     if list1[-(j 1)] == i:                         if j == 0:                             list1 = []                             break                         else:                             list1 = list1[-j:]                             break                 list1.append(i)             maxnum = max(maxnum,len(list1))         return maxnum

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 

---

567. 字符串的排列

给你两个字符串s1和s2，写一个函数来判断s2是否包含s1排列。如果是，返回true；否则，返回false。

换句话说，s1排列之一是s2的子串。

示例 1：

输入：s1 = "ab" s2 = "eidbaooo" 输出：true 解释：s2 包含 s1 的排列之一 ("ba"). 

示例 2：

输入：s1= "ab" s2 = "eidboaoo" 输出：false

class Solution(object):     def checkInclusion(self, s1, s2):         # 统计 s1 每个字符出现的次数         counter1 = collections.Counter(s1)         N = len(s2)         # 定义滑动窗的范围是 [left, right]，闭区间，长度与s1相等         left = 0         right = len(s1) - 1         # 统计窗口s2[left, right - 1]元素出现的次数         counter2 = collections.Counter(s2[0:right])         while right < N:             # 把 right 放置位置元素 counter2 中             counter2[s2[right]]  = 1             # 如果滑动窗口中各种元素的次数出现 s1 元素出现次数完全一致，返回 True             if counter1 == counter2:                 return True             # 在窗口向右移动之前，把当前 left 位置元素的数量 - 1             counter2[s2[left]] -= 1             # 如果当前 left 位置元素的数量为 0， 需要从字典中删除，否则，出现次数为 0 的元素会影响两 counter 之间的比较             if counter2[s2[left]] == 0:                 del counter2[s2[left]]             # 向右移动窗口             left  = 1             right  = 1         return False