“滑动窗口”算法实例

1 问题

给定一个字符串“S”，找出其中不含有重复字符的最长子串的长度。例如：S=‘ABCABCBB’，则不含重复字符的最长字串长度为3.。S=‘ABCDFG’,则不含重复字符的最长字串长度为6。要求设计一个Python程序实现该功能？

2 方法

按照一般方法，可以采取暴力求解，即把所有不重复的字串全部找出来，再在其中找出最长的字串。可是该方法的时间复杂度和空间复杂度都十分大，面对较长的字符串则会浪费过多时间。

对于该现象，即可使用“滑动窗口”算法。滑动窗口算法也是一种思想，是双指针的拓展和延伸。滑动：指这个窗口是移动的，也就是移动是按照一定方向来的。窗口：窗口大小并不是固定的，可以不断扩容直到满足一定的条件；也可以不断缩小，直到找到一个满足条件的最小窗口；当然也可以是固定大小。

面对前面所提出的问题，使用“滑动窗口”算法，大致思路为：

1. 设置两个指针和一个空列表
2. 固定左指针，不断右移右指针，同时更新最长不重复字符串长度
3. 如果出现重复字符，再右移左指针，如此重复，直到遍历完字符串的所有字符。 最后输出最长不重复字符串长度即可。

这样就降低了问题的复杂度，也降低了循环的嵌套深度。

代码清单 1

'''
通过固定左端元素，再右端元素不断右移，算出左端和右端间的总数
然后左端再不断右移，不断计算之间的总数。最后算出最长长度
'''
s = input() # 输入字符串
max_length =float('-inf') # 定义一个初指为负无穷
start = 0 # 定义左指针为0
l = list() # 定义一个空列表，用于是否重复的判断
for end in range(len(s)): # 右指针通过for循环，逐步向右移动
   while s[end] in l: # 当右指针移到某个值时，且该值已经在前面出现过
       l.remove(s[start]) # 移除左指针对应的重复值
       start += 1 # 并且将左指针向右移动一个单位
   max_length = max(max_length, end-start+1) # 每次右指针移动后，统计不重复的字符串的最长长度
   l.append(s[end]) # 将右指针每次遍历过的值加入列表中，用于重复判断
if max_length == float('-inf'): # 如果最大值对于负无穷，则代表无最长不重复字符串
   print('0')
else:
   print(max_length) # 打印最大不重复字符串长度
'''
测试结果：
abcabcbb 输出：3
aaaaaaaa 输出：1
'''

3 结语

通过测试，发现“滑动窗口”算法可以很好的解决该问题，与此同时，相对于暴力求解，其时间复杂度和空间复杂度也得到了优化。总结发现，一般给出的数据结构是数组或者字符串，且求取某个子串或者子序列最长最短等最值问题或者求某个目标值时。都可以使用“滑动窗口”算法。