學(xué)習(xí)如何使用Sliding Window Algorithm 攻克相關(guān)的Leetcode算法題。Leetcode上有若干滑動窗口問題，網(wǎng)絡(luò)協(xié)議上也廣泛使用了滑動窗口算法，可見這個算法的重要性。

本文參考：
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.

假設(shè)有數(shù)組[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中所包含的全部字符(包括重復(fù)的)

• 子序列長度與t相同

我們實現(xiàn)算法的最終目標就是：判斷以上三個條件是否成立。

條件1和條件3無疑很好判斷，但對于條件2，如果使用嵌套循環(huán)的方式暴力解決，時間復(fù)雜度將是O(n*m).n為s的規(guī)模，m為t的規(guī)模。

而滑動窗口算法就是為了能夠高效的判斷該條件。

思路：在s上伸縮滑動一個窗口，（注意，不止包括整體的滑動——即左右邊界同方向相同距離移動，也包括伸縮——即一個邊界動一個邊界不動），那么必然滿足條件1，接下來如果由該窗口得到的子序列滿足條件2，且滿足條件3，那么保存窗口左邊界作為結(jié)果之一。然后，繼續(xù)伸縮滑動窗口，直至得到全部結(jié)果。

具體來說:

1. 雙指針begin,end——記錄滑動窗口的左右邊界。

2. 一個Hash表——記錄的t中的所有字符(去重)以及每個字符的出現(xiàn)次數(shù)。原因：由于t中可能包含重復(fù)字符，那么不僅要依次判斷窗口子序列是否包含t中某個字符，還要判斷該字符出現(xiàn)的次數(shù)是否與在t中相同。既然字符本身和出現(xiàn)次數(shù)相關(guān)聯(lián)，那么就可以用一對鍵值對來表示，所以可使用Hash表來保存t中的字符和出現(xiàn)頻率。C++中，我們用unordered_map<char, int> map;

3. 一個計數(shù)器count，記錄t中包含的字符數(shù)(去重后），即需要判斷是否存在于t的字符。

4. 令begin = 0, end = 0;移動右邊界，每當發(fā)現(xiàn)一個字符存在于t中，遞減該字符在Hash表中出現(xiàn)頻次，即<key,value>中value的值，遞減至0時，說明該窗口子序列中至少包含了與t中相同個數(shù)的該字符，那么此時遞減count計數(shù)器，表示該字符的判斷已完成，需要判斷的字符數(shù)-1.

5. 以此類推，不斷拓展右邊界，直至count為0，表示窗口序列中已經(jīng)至少包含了t中所有字符（包括重復(fù)的）。

6. 分析此時的窗口子序列，t是該序列的子集，條件2已滿足。如果兩者長度相同，即滿足條件3，那么它的左邊界begin就是我們想要的結(jié)果之一了。但我們不會一直那么幸運，這時就需要收縮窗口的左邊界，即end不動，begin向右移動遍歷該子序列，直至找到t中包含的字符，此時再次計算end-begin的值，與t長度比較，判斷是否是想要的結(jié)果。而找到上述字符后，字符頻次加1，如加1后該字符頻次仍小于0，說明該字符有冗余，而出現(xiàn)頻次大于0，則count加1，這是告訴我們有一個字符需要重新被判斷了，因為無論它是不是我們想要的，都不能再用了，需要繼續(xù)向右拓展窗口從新找起。

7. 當count != 0時，繼續(xù)向右拓展窗口，直至count為0，然后判斷條件3的同時，向右移動begin遍歷子序列，直至count != 0,以此類推。

（為了弄清思路的細節(jié)，寫了一大堆的文字，實在是辛苦。）

上面是文字形式的分析，如果看不懂，那么應(yīng)結(jié)合圖表推演分析。且真正分析算法問題時，應(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;
        
    }
};