滑动窗口法练习题
# 滑动窗口法模板
# step1 定义需要维护的变量(通常是最大长度,最小长度,和,哈希表等)
x, y = ...
# step2 定义窗口首尾端,根据条件要求,滑动窗口
start = 0
for end in range(len):
# step3 更新需要维护的变量,某些需要if来判断是否更新
x = new_x
if condition: y = new_y
#step 4 - 情况1 题目要求窗口长度固定,用if判断是否达到要求长度
if 长度达到要求:
# 达到长度则左指针向前移动一个格,保证下次右指针移动时长度固定
# 移动左指针前,将变量更新
#step 4 - 情况2 如果窗口长度无特殊要求,一般会涉及窗口内元素是否合法
# 窗口不合法,用while移动左指针一直到合法为止
while 不合法:
# 更新变量,移动窗口
return ans
LC3 无重复字符的最小子串
LC159 至多包含两个不重复字符的最长子串
LC1695 删除子数组的最大得分
LC438 寻找字母异位词
LC209 长度最小子数组
LC643 子数组的最大平均数
LC485、487、1004 最大连续1的个数:
LC1208 尽可能使字符串相等
LC1052 爱生气的书店老板
LC1423 首尾拿牌可能获得的最大点数
LC1151 最小交换次数
LC76 最小覆盖子串
LC1588 所有奇数长度子数组的和
原文:https://www.cnblogs.com/xhmorehair/p/15306667.html