字符串系列之滑动窗口
大家好，滑动窗口算法一般是作用在字符串或者数组上，通过不断的滑动逻辑窗口，在特定窗口大小内进行计算的过程。滑动窗口的方式可以降低时间复杂度，从而减短计算的执行时间。
比如说在字符串s="5189623196" 中，窗口大小 w=5，找出每个窗口字符子串的和。
普通的计算方式：每 5 个进行一次求个计算，时间复杂度方面能够达到 O(N^2)。
利用窗口的方式：可很大程度可以减小时间方面的消耗。就拿引例来说，时间复杂度应该是O(N)的线性复杂度。
其核心思路是：窗口在每一次的滑动前后，中间元素内容没有改变，仅仅改变的是开头和结尾元素，即：下一窗口内元素之和 = 上一窗口元素和 - 离开窗口元素值 + 新加入窗口元素值。
下面分步骤进行讨论，将最终结果写入到 res 中。
步骤一：直接计算窗口内元素和，res = [29]
步骤二：在上一步骤的基础上，减去离开窗口的元素，加上新加入窗口的元素。
步骤三：继续在上一步骤的基础上，减去离开窗口的元素，加上新加入窗口的元素
相同逻辑继续执行....
步骤六：滑动窗口将最后一个元素包含进来
上述每一步骤中，将 sum 值都添加到最终的结果变量 res 中。滑动窗口这样的思维方式就很巧妙的进行在窗口的不断移动，进而产生各元素在窗口边界进进出出，利用这一点，在时间复杂度方面进行了一个很大提升。
Python代码如下：
class Solution(object):
def sumSlidingWindow(self, s, w):
sum = 0
res = []
# 计算第一个窗口数字之和
for item in range(5):
sum += s[item]
res.append(sum)
# 后面利用滑动窗口思想进行计算
for item in range(w, len(s)):
sum -= s[item-w]
sum += s[item]
res.append(sum)
return res下面用两个 LeetCode 经典案例进一步阐述滑动窗口这类题目。
1.字符串的排列
给两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
输入：s1 = "ab" s2 = "eidbaooo" 输出：true 解释：s2 包含 s1 的排列之一 ("ba").
首先，两个字符串的排列，首先可以想到字典，根据字典去比较。词典可根据两个不同字符串将给到的字符进行计数，因此，这样很同容易进行比较。
另外，在遍历 s2 的时候，使用滑动窗口，该窗口的长度是字符串 s1 的长度，遍历 s2 使得字符不断的出入，在此过程中比较两个字典。
整个过程，记 s1 的长度为 size1，s2 的长度为 size2，窗口大小为 size1，不断遍历 s2，直到 s2 的结尾。
记 s1 的字典为 dict_s1，记s1的字典为dict_s2，在遍历s2的过程中，每滑动一次窗口，比较 dict_s1 和 dict_s2 是否相等。
窗口滑动过程中，需要删除滑出窗口的元素以及新增滑入窗口的元素。
删除滑出窗口的元素：广义上是从字典 dict_s2 中删除，注意此处不能直接删除，因为可能会有重复元素存在，比如：{'a':2}，所以只能是将 value 值减 1。之后再判断 value 值为否为 0，如果为 0 了，这个时候就可以直接将该元素从字典中删除。
新增滑入窗口的元素：直接将滑入窗口的元素添加进字典中。
下面用几个图清晰的一步一步操作：
初始化 s1 对应的字典 dict_s1={'a':1,'b':1}
① s2 对应的字典为图中窗口中的元素 dict_s2={'e':1,'i':1}。
最后判断 dict_s1 != dict_s2
② 向右滑动窗口，由于元素e的 value 值为 1，直接删除该元素，加入新元素d，此时，dict_s2={'i':1,'d':1}。
最后判断 dict_s1 != dict_s2
③ 继续向右滑动窗口，由于元素 i 的 value 值为 1，直接删除该元素，加入新元素 b，此时，dict_s2={'d':1,'b':1}。
最后判断 dict_s1 != dict_s2
③ 继续向右滑动窗口，由于元素 d 的 value 值为 1，直接删除该元素，加入新元素 a，此时，dict_s2={'b':1,'a':1}。
最后判断 dict_s1 == dict_s2，此时可以直接返回 True。不用在继续窗口滑动了。
这个题虽然在 LeetCode 中标记为中等，但是用滑动窗口的方式去解决还是非常容易理解的。
下面是 Python 代码的实现：
class Solution(object):
def checkInclusion(self, s1, s2):
size1 = len(s1)
size2 = len(s2)
if size1 > size2:
return False
dict_s1 = collections.Counter(s1)
dict_s2 = collections.Counter(s2[:size1-1])
left = 0
for right in range(size1-1, size2):
# 增加新添加的元素
dict_s2[s2[right]] += 1
# 判断如果字典相同，则返回 True
if dict_s1 == dict_s2:
return True
# 删除左边剔除的元素(首先需要将左边元素的 value 值减 1)
dict_s2[s2[left]] -= 1
# value 值为 0 的时候，就可以删除该元素了
if dict_s2[s2[left]] == 0:
del(dict_s2[s2[left]])
# 窗口整体向右移动一格
left += 1
right += 1
return False2.无重复字符的最长子串
给定一个字符串
s，请你找出其中不含有重复字符的 最长子串 的长度。输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
想要判断字符是否存在，通常会使用到字典结构来判断是否存在。
首先，初始化窗口左右端 left=0 和 right=0，初始化字典 words 用来存放已加入字符的元素（key）和元素下标（value），例如，words={'a':0,'b':1,'c':2}
然后，right 指针向右移动，判断新加入元素是否存在于字典中，如果存在，让窗口左边界指向字典对应 value 值的下一个位置，并且更新字典中对应元素的下标值（value）；如果不存在，则加入字典 words中；
注意点：
中间有可能 left 已经更新到后边，而新判断的元素可能在前面，会导致 left 变小，所以需要采用 max 来进行判断
举例：abba，执行到第二个 b 的时候，left=2，此时words={'a':0,'b':2}。后面再判断最后的 a 的时候，就会使得 left=0+1=1
因此，需要 left = max(words.get(v) + 1, left)
每一步骤记录最长子串长度，依旧用几个图清晰的一步一步操作：
① left=0, right=0, 加入新元素 'a'，words={'a':0}, 窗口长度为1。
② left=0, right=1, 加入新元素 'b'，words={'a':0, 'b':1}, 窗口长度为2。
③ left=0, right=2, 加入新元素 'c'，words={'a':0, 'b':1, 'c':2}, 窗口长度为3。
④ left=0, right=3, 加入新元素 'a';
发现 a 已经在 words={'a':0, 'b':1, 'c':2} 存在；
则更新 left=max(words.get('a') + 1, left)=1，words={'a':3, 'b':1, 'c':2}，窗口长度为3。
⑤ left=1, right=4, 加入新元素 'b';
发现 'b' 已经在 words={'a':3, 'b':1, 'c':2} 存在；
则更新 left=max(words.get('b') + 1, left)=2，words={'a':3, 'b':4, 'c':2}，窗口长度为3。
⑥ left=2, right=5, 加入新元素 'c';
发现 'c' 已经在 words={'a':3, 'b':4, 'c':2} 存在；
则更新 left=max(words.get('c') + 1, left)=3，words={'a':3, 'b':4, 'c':5}，窗口长度为3。
⑦ left=3, right=6, 加入新元素 'b';
发现 b 已经在 words={'a':3, 'b':4, 'c':5} 存在；
则更新 left=max(words.get('b') + 1, left)=5，words={'a':3, 'b':6, 'c':5}，窗口长度为2。
⑧ left=5, right=7, 加入新元素 'b';
发现 'b' 已经在 words={'a':3, 'b':6, 'c':5} 存在；
则更新 left=max(words.get('b') + 1, left)=7，words={'a':3, 'b':7, 'c':5}，窗口长度为1。
根据每一步骤记录的窗口长度，可得到最长窗口为 3。下面就由上述逻辑得到最终的代码：
class Solution(object):
def lengthOfLongestSubstring(self, s):
if not s:
return 0
left, right = 0, 0
length = 1
words = {}
for right, v in enumerate(s):
if s[right] in words.keys():
print(words.get(v) + 1, left)
left = max(words.get(v) + 1, left)
length = max(right-left+1, length)
# 将当前值的 value 值覆盖
words[v] = right
print(words)
return length综上所述，本文字符串系列有关滑动窗口的介绍已经完成，关于其他滑动窗口问题以后会继续总结。
原文地址：https://blog.csdn.net/csdn1561168266/article/details/135708360
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！