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 retclass 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 retclass 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