Sliding Window Algorithm(滑动窗口算法）
学习如何使用Sliding Window Algorithm 攻克相关的Leetcode算法题。Leetcode上有若干滑动窗口问题，网络协议上也广泛使用了滑动窗口算法，可见这个算法的重要性。
本文参考：
1.https://leetcode.com/problems/find-all-anagrams-in-a-string/discuss/92007/Sliding-Window-algorithm-template-to-solve-all-the-Leetcode-substring-search-problem.
2.https://stackoverflow.com/questions/8269916/what-is-sliding-window-algorithm-examples
3.http://www.codingalpha.com/sliding-window-algorithm-c-program/
什么是滑动窗口算法？
The Sliding Problem contains a sliding window which is a sub – list that runs over a Large Array which is an underlying collection of elements.
假设有数组[a b c d e f g h]
一个大小为3的滑动窗口在其上滑动，则有:
[a b c]
[b c d]
[c d e]
[d e f]
[e f g]
[f g h]
滑动窗口算法对比与分析
——待添加
滑动窗口问题实例
一、FInd All Anagrams in a String
分析：对于string s 和 string t，查找s中t的同字母异序词子序列。那么这个子序列很明显有三点非常明显的特征：
-
是s的子序列
-
包含t中所包含的全部字符(包括重复的)
-
子序列长度与t相同
我们实现算法的最终目标就是：判断以上三个条件是否成立。
条件1和条件3无疑很好判断，但对于条件2，如果使用嵌套循环的方式暴力解决，时间复杂度将是O(n*m).n为s的规模，m为t的规模。
而滑动窗口算法就是为了能够高效的判断该条件。
思路：在s上伸缩滑动一个窗口，（注意，不止包括整体的滑动——即左右边界同方向相同距离移动，也包括伸缩——即一个边界动一个边界不动），那么必然满足条件1，接下来如果由该窗口得到的子序列满足条件2，且满足条件3，那么保存窗口左边界作为结果之一。然后，继续伸缩滑动窗口，直至得到全部结果。
具体来说:
-
双指针begin,end——记录滑动窗口的左右边界。
-
一个Hash表——记录的t中的所有字符(去重)以及每个字符的出现次数。原因：由于t中可能包含重复字符，那么不仅要依次判断窗口子序列是否包含t中某个字符，还要判断该字符出现的次数是否与在t中相同。既然字符本身和出现次数相关联，那么就可以用一对键值对来表示，所以可使用Hash表来保存t中的字符和出现频率。C++中，我们用unordered_map<char, int> map;
-
一个计数器count，记录t中包含的字符数(去重后），即需要判断是否存在于t的字符。
-
令begin = 0, end = 0;移动右边界，每当发现一个字符存在于t中，递减该字符在Hash表中出现频次，即<key,value>中value的值，递减至0时，说明该窗口子序列中至少包含了与t中相同个数的该字符，那么此时递减count计数器，表示该字符的判断已完成，需要判断的字符数-1.
-
以此类推，不断拓展右边界，直至count为0，表示窗口序列中已经至少包含了t中所有字符（包括重复的）。
-
分析此时的窗口子序列，t是该序列的子集，条件2已满足。如果两者长度相同，即满足条件3，那么它的左边界begin就是我们想要的结果之一了。但我们不会一直那么幸运，这时就需要收缩窗口的左边界，即end不动，begin向右移动遍历该子序列，直至找到t中包含的字符，此时再次计算end-begin的值，与t长度比较，判断是否是想要的结果。而找到上述字符后，字符频次加1，如加1后该字符频次仍小于0，说明该字符有冗余，而出现频次大于0，则count加1，这是告诉我们有一个字符需要重新被判断了，因为无论它是不是我们想要的，都不能再用了，需要继续向右拓展窗口从新找起。
-
当count != 0时，继续向右拓展窗口，直至count为0，然后判断条件3的同时，向右移动begin遍历子序列，直至count != 0,以此类推。
（为了弄清思路的细节，写了一大堆的文字，实在是辛苦。）
上面是文字形式的分析，如果看不懂，那么应结合图表推演分析。且真正分析算法问题时，应该在脑中或者草稿纸上构思出具体的图画。
//该例子来自于leetcode
Input:
s: "cbaebabacd" p: "abc"
Output:
[0, 6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".
滑动窗口序列变化示意图
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> result;
if(s.empty() || p.empty()) return result;
if(p.size() > s.size()) return result;
unordered_map<char, int> map;
for(char c : p)
{
map[c] = map[c] + 1;
}
size_t count = map.size();
int begin = 0, end = 0;
while(end < s.size())
{
if(map.find(s.at(end)) != map.end())
{
map[s.at(end)]--;
if(map[s.at(end)] == 0){ count--; }
}
++end;
while(count == 0)
{
if(map.find(s.at(begin)) != map.end())
{
map[s.at(begin)]++;
if(map[s.at(begin)] > 0){ count++; }
}
if(end - begin == p.size())
{
result.push_back(begin);
}
++begin;
}
}
return result;
}
};
