LeetCode 0003 无重复字符的最长子串 (中等, 2022-02)剑指Offer 5901 滑动窗口的最大值 (困难, 2022-01)牛客 0028 最小覆盖子串 (较难, 2022-02)牛客 0041 最长无重复子数组 (中等, 2022-03)
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。- 维护一个已经出现过的字符集合，详见代码；
Python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
used = set()
l = r = 0 # 窗口边界
ret = 0
while r < len(s):
while s[r] in used: # 如果已经出现过则移出
# 注意这里要 while 判断，因为 l 指针不一定刚好指向这个重复的字符，要一直移动直到把 r 指向的字符移出
used.remove(s[l])
l += 1
ret = max(ret, r - l + 1)
used.add(s[r])
r += 1
return ret优化：直接移动 l 指针到重复字符的下一个位置，减少 l 指针移动；
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
used = dict()
l = r = 0 # [l, r] 闭区间
ret = 0
while r < len(s):
if s[r] in used and l <= used[s[r]]: # l <= used[s[r]] 的意思是重复字符出现在窗口内；
l = used[s[r]] + 1
ret = max(ret, r - l + 1)
used[s[r]] = r
r += 1
return ret
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。详细描述
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
提示：
你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。- 使用单调队列维护一个最大值序列，每次滑动窗口前，更新单调队列，使队首元素为下一个窗口中的最大值，详见参考链接或具体代码；
Python
- 跟官方写法的区别：
- 官方的单调队列维护的是数组下标，通过判断下标位置来确定是否移除队首元素；因此可以使用严格单调队列；而下面的写法中使用值来判断是否移除队首，因此使用的是非严格单调队列（相关代码段：
if q[0] == nums[i - k]: q.popleft()）
- 官方的单调队列维护的是数组下标，通过判断下标位置来确定是否移除队首元素；因此可以使用严格单调队列；而下面的写法中使用值来判断是否移除队首，因此使用的是非严格单调队列（相关代码段：
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
from collections import deque
if not nums: return []
# 初始化单调队列，对任意 i > j，有 q[i] >= q[j]
q = deque()
for x in nums[:k]:
while q and q[-1] < x: # 注意这里是非严格单调的
q.pop()
q.append(x)
# print(q)
ret = [q[0]] #
for i in range(k, len(nums)):
if q[0] == nums[i - k]: # 因为是通过值判断，所以需要保留所有相同的最大值，所以队列是非严格单调的
q.popleft()
while q and q[-1] < nums[i]:
q.pop()
q.append(nums[i])
ret.append(q[0])
# print(q)
return ret
给出两个字符串 s 和 t，要求在 s 中找出最短的包含 t 中所有字符的连续子串。- 应用模板比较复杂的一题；
滑动窗口模板
l = r = 0 # 初始化 [l, r] 闭区间
while r < N:
# 更新窗口
while check(): # 满足要求进入循环，不满足退出
# 更新答案
l += 1 # 移动左边界
r += 1 # 移动右边界Python
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param S string字符串
# @param T string字符串
# @return string字符串
#
class Solution:
def minWindow(self , S: str, T: str) -> str:
# write code here
from collections import Counter, defaultdict
l, r = 0, 0
N = len(S)
ret = S # 初始化为最大的可能，但是注意，可能有无结果的情况，所以还需要一个变量记录答案是否存在
flag = -1 # 记录是否出现过匹配串，避免无答案的情况
need = Counter(T)
used = defaultdict(int)
def check(): # 检验是否满足情况
for k, v in need.items():
if k not in used or used[k] < need[k]:
return False
return True
while r < N:
used[S[r]] += 1
while check():
flag = 1
if r - l < len(ret):
ret = S[l: r + 1]
used[S[l]] -= 1
l += 1
r += 1
return ret if flag != -1 else ''
给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组- 标准的滑动窗口模板问题；
Python
class Solution:
def maxLength(self , arr: List[int]) -> int:
if not arr: return 0
N = len(arr)
l, r = 0, 0 # [l, r] 滑动窗口闭区间
ret = 1
book = set()
while r < N:
# 当不满足条件时，循环移动左边界直到再次满足
while arr[r] in book: # 注意这里判断的是 arr[r]
book.remove(arr[l]) # 这里移除的是 arr[l]
l += 1
ret = max(ret, r - l + 1) # 更新结果
book.add(arr[r])
r += 1
return ret