學(xué)習(xí)如何使用Sliding Window Algorithm 攻克相關(guān)的Leetcode算法題。Leetcode上有若干滑動(dòng)窗口問題，網(wǎng)絡(luò)協(xié)議上也廣泛使用了滑動(dòng)窗口算法，可見這個(gè)算法的重要性。
本文參考：
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/
什么是滑動(dòng)窗口算法居夹？
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.
假設(shè)有數(shù)組[a b c d e f g h]
一個(gè)大小為3的滑動(dòng)窗口在其上滑動(dòng)，則有:
[a b c]
[b c d]
[c d e]
[d e f]
[e f g]
[f g h]
滑動(dòng)窗口算法對(duì)比與分析
——待添加
滑動(dòng)窗口問題實(shí)例
一、FInd All Anagrams in a String
分析：對(duì)于string s 和 string t准脂，查找s中t的同字母異序詞子序列劫扒。那么這個(gè)子序列很明顯有三點(diǎn)非常明顯的特征：
是s的子序列
包含t中所包含的全部字符(包括重復(fù)的)
子序列長(zhǎng)度與t相同
我們實(shí)現(xiàn)算法的最終目標(biāo)就是：判斷以上三個(gè)條件是否成立。
條件1和條件3無疑很好判斷意狠，但對(duì)于條件2粟关，如果使用嵌套循環(huán)的方式暴力解決，時(shí)間復(fù)雜度將是O(n*m).n為s的規(guī)模环戈，m為t的規(guī)模。
而滑動(dòng)窗口算法就是為了能夠高效的判斷該條件澎灸。
思路：在s上伸縮滑動(dòng)一個(gè)窗口院塞，（注意，不止包括整體的滑動(dòng)——即左右邊界同方向相同距離移動(dòng)性昭，也包括伸縮——即一個(gè)邊界動(dòng)一個(gè)邊界不動(dòng)）拦止，那么必然滿足條件1，接下來如果由該窗口得到的子序列滿足條件2糜颠，且滿足條件3汹族，那么保存窗口左邊界作為結(jié)果之一。然后其兴，繼續(xù)伸縮滑動(dòng)窗口顶瞒，直至得到全部結(jié)果。
具體來說:
雙指針begin,end——記錄滑動(dòng)窗口的左右邊界元旬。
一個(gè)Hash表——記錄的t中的所有字符(去重)以及每個(gè)字符的出現(xiàn)次數(shù)榴徐。原因：由于t中可能包含重復(fù)字符，那么不僅要依次判斷窗口子序列是否包含t中某個(gè)字符匀归，還要判斷該字符出現(xiàn)的次數(shù)是否與在t中相同坑资。既然字符本身和出現(xiàn)次數(shù)相關(guān)聯(lián)，那么就可以用一對(duì)鍵值對(duì)來表示穆端，所以可使用Hash表來保存t中的字符和出現(xiàn)頻率袱贮。C++中，我們用unordered_map<char, int> map;
一個(gè)計(jì)數(shù)器count体啰，記錄t中包含的字符數(shù)(去重后）攒巍，即需要判斷是否存在于t的字符。
令begin = 0, end = 0;移動(dòng)右邊界狡赐，每當(dāng)發(fā)現(xiàn)一個(gè)字符存在于t中窑业，遞減該字符在Hash表中出現(xiàn)頻次，即<key,value>中value的值枕屉，遞減至0時(shí)常柄，說明該窗口子序列中至少包含了與t中相同個(gè)數(shù)的該字符，那么此時(shí)遞減count計(jì)數(shù)器，表示該字符的判斷已完成西潘，需要判斷的字符數(shù)-1.
以此類推卷玉，不斷拓展右邊界，直至count為0喷市，表示窗口序列中已經(jīng)至少包含了t中所有字符（包括重復(fù)的）相种。
分析此時(shí)的窗口子序列，t是該序列的子集品姓，條件2已滿足寝并。如果兩者長(zhǎng)度相同，即滿足條件3腹备，那么它的左邊界begin就是我們想要的結(jié)果之一了衬潦。但我們不會(huì)一直那么幸運(yùn)，這時(shí)就需要收縮窗口的左邊界植酥，即end不動(dòng)镀岛，begin向右移動(dòng)遍歷該子序列，直至找到t中包含的字符友驮，此時(shí)再次計(jì)算end-begin的值漂羊，與t長(zhǎng)度比較，判斷是否是想要的結(jié)果卸留。而找到上述字符后走越，字符頻次加1，如加1后該字符頻次仍小于0艾猜，說明該字符有冗余买喧，而出現(xiàn)頻次大于0，則count加1匆赃，這是告訴我們有一個(gè)字符需要重新被判斷了淤毛，因?yàn)闊o論它是不是我們想要的，都不能再用了算柳，需要繼續(xù)向右拓展窗口從新找起低淡。
當(dāng)count != 0時(shí)，繼續(xù)向右拓展窗口瞬项，直至count為0蔗蹋，然后判斷條件3的同時(shí)，向右移動(dòng)begin遍歷子序列囱淋，直至count != 0,以此類推猪杭。
（為了弄清思路的細(xì)節(jié)，寫了一大堆的文字妥衣，實(shí)在是辛苦皂吮。）
上面是文字形式的分析戒傻，如果看不懂，那么應(yīng)結(jié)合圖表推演分析蜂筹。且真正分析算法問題時(shí)需纳，應(yīng)該在腦中或者草稿紙上構(gòu)思出具體的圖畫。
//該例子來自于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;
}
};
