滑动窗口模板
模板
def temp(s: Sequence):
l = r = 0 # 初始化窗口, [l, r] 闭区间
while r < len(s):
... # 更新缓存
while check(): # 检查条件
... # 更新缓存或答案
l += 1 # 移动左边界, 缩小窗口
... # 更新缓存或答案
r += 1 # 移动右边界, 扩大窗口以上是滑动窗口的基础模板;
更新缓存和检查条件的先后顺序要看具体情况, 详见示例;
示例
长度最小的子数组
问题简述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组，并返回其长度。
如果不存在符合条件的子数组，返回 0 。class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
ret = 0
s = 0 # 记录当前窗口的和
l, r = 0, 0
while r < len(nums):
s += nums[r] # 更新缓存
while s >= target:
if not ret or r - l + 1 < ret: # 更新答案
ret = r - l + 1
s -= nums[l]
l += 1
r += 1
return ret无重复字符的最长子串
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
used = set() # 记录已经出现过的字符
ret = 0 # 记录最大长度
l = r = 0 # 窗口边界
while r < len(s):
while s[r] in used: # 出现重复字符, 滑动左边界
# 移除最左边界的字符, 并缩小窗口
used.remove(s[l]) # 更新缓存
l += 1
# 更新缓存和答案
ret = max(ret, r - l + 1)
used.add(s[r])
r += 1 # 扩大窗口
return ret最小覆盖子串
class Solution:
def minWindow(self, s: str, t: str) -> str:
from collections import Counter, defaultdict
l, r = 0, 0
ret = '' # 记录答案
need = Counter(t) # 需要满足的每种字符数
book = defaultdict(int) # 记录出现过的字符数
def check(): # 检验是否满足情况
return all(book[k] >= need[k] for k in need)
while r < len(s):
book[s[r]] += 1 # 更新缓存
while check(): # 条件检查
if not ret or r - l < len(ret): # 更新答案
ret = s[l: r + 1]
book[s[l]] -= 1
l += 1
r += 1
return ret更多问题
algorithms/滑动窗口
Last updated