一 滑动窗口
幻灯片11.jpg
滑动窗口法（sliding window）常用于输入为数组，输出为统计满足特定约束条件的子串次数的情况。
通常情况下，滑动窗口法可以考虑为暴力双循环算法的优化，根据所要求子串的性质，减少遍历次数。具体在实现过程中，根据子串所要求的性质，可以采用数据结构来保存窗口的信息，便于信息的存取，常用的数据结构有：
- SortedList (sortedcontainers)
- dict
- list
在滑动窗口解决中，重要的一步是判断窗口左端left和窗口右端right的更新条件。通常滑动窗口右端right是按照逐步迭代，而窗口左端left则在满足子串约束条件的情况下，从左到右，或从右到左进行遍历，相当于缩小窗口。注意l和r均为往右移动，只不过r是一次一步，l是根据子串性质，可一次多步。
考虑：Leetcode 1100. 长度为 K 的无重复字符子串
给你一个字符串 S，找出所有长度为 K 且不含重复字符的子串，请你返回全部满足要求的子串的 数目。
示例 1：
输入：S = "havefunonleetcode", K = 5
输出：6
解释：
这里有 6 个满足题意的子串，分别是：'havef','avefu','vefun','efuno','etcod','tcode'。
示例 2：
输入：S = "home", K = 5
输出：0
解释：
注意：K 可能会大于 S 的长度。在这种情况下，就无法找到任何长度为 K 的子串。
解题思路: 考虑从左到右遍历数组，Pos记录某元素出现的位置信息，对于新增元素s[r],若未出现在Pos中，则窗口右端右移一步并更新Pos，如果已出现在Pos中，则窗口左端l右移到s[l:r]满足没有重复元素性质的位置，本题中为重复元素首次出现位置的右边一步，如下图所示。
幻灯片11.jpg
幻灯片12.jpg
幻灯片14.jpg
参考题解：滑动窗口法解决长度为K的无重复子串问题(含图文实例详解)
class Solution:
def numKLenSubstrNoRepeats(self, S: str, K: int) -> int:
pos = {}
l = r = 0
count = 0
while (r < len(S)):
if S[r] not in pos:
pos[S[r]] = r
else:
# 删除l到pos[S[r]]的元素信息
start = pos[S[r]] + 1
for i in range(l, pos[S[r]] + 1):
del pos[S[i]]
l = start
pos[S[r]] = r
if len(pos) == K:
count += 1
del pos[S[l]]
l += 1
r += 1
return count
二 滑动窗口解决框架
滑动窗口法重点在于是根据特定子串的性质，来维护某数据结构信息，以此来减少暴力枚举的迭代次数，形象上像窗口右端不断蠕动，窗口左端不断跟进的滑动过程。某些情况下，特定子串的性质可以用表格记录，因此这时也可采用动态规划法。
滑动窗口法代码大体框架如下：
#滑动窗口解决框架
def solution(nums):
#保存特定信息的数据结构
structure = DataStructure()
#窗口左端left和窗口右端right
l = r =0
#满足约束条件的子串数
res = 0
while r<len(nums):
#加入第r个节点，更新datastructure的性质
structure.add(nums[r])
#nums[r]加入struture后满足某种条件
if structure.satisfy_condition():
#则更新datastruture的性质
structure.update()
#nums[r]不满足某种条件
else:
#从左到右或从右到左更新窗口左端l，l根据子串约束的性质，
#移动到窗口[l:r]满足约束性质为止。
while not structure.satisfy_condition():
l+=1
structure.remove(nums[l])
#更新满足约束的子串个数
update(res)
#窗口右端往右移动一格
r+=1
return res
三 Leetcode例题
很多习题可供参考，列出一部分和题解如下：
-
3 剑指 Offer 57 - II. 和为s的连续正数序列 -暴力枚举法 -函数解析法 -滑动窗口法 - 参考题解和为s的连续正数序列
-
8 q567. 字符串的排列 -暴力法 -滑动窗口法
-
12 239. 滑动窗口最大值 -偷懒解法滑动窗口+sortedlist
-
13 978. 最长湍流子数组 -滑动窗口法
网友评论