很多子序列题都可以用滑动窗口解决，这个方案适用于需要找一个子序列的开始和结束位置。注意，这里指的子序列类似于子字符串，而非subsequence。
例如 leetcode 的 Substring with Concatenation of All Words 。最简单的方法就是找到一个开始位置，然后判断这个位置是否可行，代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#!/usr/bin/env python class Solution: def findSubstring(self, s, words): if len(words) == or len(s) == : return [] dic = {} count = for w in words: dic[w] = dic.get(w, ) + 1 count += 1 lw = len(words[]) lws = lw * len(words) result = [] for i in xrange(len(s) - lws + 1): if self.possible(s, lw, i, dic, count): result.append(i) return result def possible(self, s, lw, i, dic, count): dic2 = dic.copy() if count == : return True while count > : cur = s[i:i+lw] if dic2.get(cur) != None and dic2.get(cur) > : dic2[cur] -= 1 if dic2[cur] < : return False count -= 1 i += lw else: return False return True |
但是时间复杂度度也很高，有O(n2)，这里面有很多冗余计算，比如对于输入
“aabbccaadd”, [“aa”, “bb”, “cc”, “dd”]
就会处理 “bbccaa” 两次。最好的办法是使用滑动窗口：维护开始和结束位置，一旦开始和结束位置一样就退出循环，否则在可行的情况下增加结束位置，如果不可行则增加开始位置。
滑动窗口可以将复杂度降低到O(n)。在这一题中，由于字典中的字符串都是同样大小，所以可以以这个大小作为步长移动。但是需要添加另一个循环来覆盖以不同的偏移开始计算的情况。代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#!/usr/bin/env python class Solution(object): def findSubstring(self, s, words): if len(s) == or len(words) == : return [] m = {} count = for w in words: m[w] = m.get(w, ) + 1 count += 1 lw = len(words[]) result = [] for delta in xrange(lw): i = delta while i < len(s) - lw + 1: key = s[i:i + lw] if m.get(key) > : m[key] -= 1 count -= 1 j = i + lw while i < j: if count == : result.append(i) if j < len(s) - lw + 1: key = s[j:j + lw] if m.get(key) > : m[key] -= 1 count -= 1 j += lw continue m[s[i:i + lw]] += 1 count += 1 i += lw else: i += lw return result |
其中，for循环用来处理不同偏移的情况，for循环中的循环用于实现滑动窗口。这个实现复杂度为O(lw * n)，如果将lw看成常数则复杂度为O(n)。
滑动窗口适用于很多子序列类的算法，如：Minimum Size Subarray Sum，Minimum Window Substring，Longest Substring Without Repeating Characters。