今天做了幾道滑動窗口的題，稍微總結(jié)一下。
起因源于早上在leetcode上pick one，隨機到了一個easy的題目，想著隨便做了，結(jié)果半天也找不到最優(yōu)解，耗時300多ms，A是A了，不過就是暴力罷了。
題目是：Find All Anagrams in a String，鏈接在https://leetcode.com/problems/find-all-anagrams-in-a-string/ ，題目就不過多解釋了。
采用的方法是滑動窗口的方法，可以說這基本是一類方法，leetcode上有幾道題都可以用相同的思想，有點類似動態(tài)規(guī)劃，在大致思想步驟一致的前提下，每個題有各自不同的“條件式”。

滑動窗口思想

滑動窗口，就是利用雙指針技巧，以及map數(shù)據(jù)結(jié)構(gòu)，維護一個不斷擴展、伸縮的窗口，在窗口內(nèi)探測記錄我們感興趣的結(jié)果。比如這道題目，以用例分析：

Input:
s: “cbaebabacd” p: “abc”

Output:
[0, 6]

首先，先構(gòu)造一個map，對于p中的每個字符char，都有map[char]++。
然后，初始化一個長度為0的窗口，left = 0，right = 0。第一步先擴展窗口，也就是在right的右邊界上做文章。每次right讀到一個字符char，都有map[char]–。當map[char]的值大于等于1時，很明顯就是窗口中進入了一個p中含有的字符。我們可以取一個變量count，值為p中所有字符的總數(shù)。每次有一個p中字符進入窗口，則count–。這樣，當count == 0的時候，表明我們的窗口中包含了p中的全部字符，得到一個結(jié)果。
當窗口包含一個結(jié)果以后，為了進一步遍歷，我們需要縮小窗口使窗口不再包含全部的p，同樣，如果map[char]>=0，表明一個在p中的字符就要移除窗口，那么count ++，以此類推。
最終代碼如下：

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        ArrayList<Integer> result = new ArrayList<>();
        if(s == null || p == null) return result;
        int left = 0,right =0,count = p.length();
        int[] map = new int[256];
        char[] sc = s.toCharArray();
        for (char c : p.toCharArray()) map[c] ++;
        while (right < s.length()) {
            if (map[sc[right++]]-->=1) count --;
            if (count == 0) result.add(left);
            if (right - left == p.length() && map[sc[left++]]++ >=0) count++;
        }
        return result;
    }
}

方法小結(jié)

可以說滑動窗口這種思想，關鍵點在于：
1、map中存儲值的意義
2、窗口什么時候擴展和收縮，對應于left和right值什么時候發(fā)生變化。
在解題的時候，首先嘗試擴展窗口right，看看什么時候包含了一個結(jié)果，記錄結(jié)果。然后縮小左邊界left，直到窗口不在包含一個可能解！接著就可以繼續(xù)擴展窗口了，以此類推。

由此，可以得到一個模板：

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        ArrayList<Integer> result = new ArrayList<>();
        if(s == null || p == null) return result;
        int left = 0,right =0,count = p.length();

        int[] map = new int[256];
        char[] sc = s.toCharArray();
        //初始化map
        for (char c : p.toCharArray()) map[c] ++;
        while (right < s.length()) {
            //1：擴展窗口，窗口中包含一個T中子元素，count--；
            //2：通過count或其他限定值，得到一個可能解。
            //3：只要窗口中有可能解，那么縮小窗口直到不包含可能解。         
        }
        return result;
    }
}

比如leetcode另一個題目 Minimum Window Substring：https://leetcode.com/problems/minimum-window-substring/。

用例是：
S = “ADOBECODEBANC”
T = “ABC”
Minimum window is “BANC”.

了解了第一道題目以后，這道題目也很容易思考出來。解題時，按照步驟：

1. 擴展窗口，窗口中包含一個T中子元素，count–；
2. 通過count或其他限定值，得到一個可能解。
3. 只要窗口中有可能解，那么縮小窗口直到不包含可能解。

首先，維護一個map，一個窗口。先看右邊界，當窗口擴展包含全部ABC時停下，這個時候必然有count == 0。但是，這個時候的結(jié)果字符串可能很長，所以我們要接著縮小左邊界。同時，當count == 0時，我們要一直縮小左邊界以找到更短的字符串。慢慢count>0了，表明窗口中不包含全部的T了，那么又要擴展窗口。依次類推，最終找到最短字符串。
套用模板，代碼如下：

public class Solution {
    public String minWindow(String s, String t) {
        int[] map = new int[256];
        int left = 0,right = 0,count = t.length(), minLen = Integer.MAX_VALUE;
        String result = "";
        for (char tc : t.toCharArray()) map[tc]++;
        char[] sc = s.toCharArray();
        while (right < s.length()|| count ==0) {
            if (count == 0){
                if (right-left+1<minLen){
                    minLen = right - left +1;
                    result = s.substring(left,right);
                }
                if (map[sc[left++]]++>=0) count++;
            }else {
                if ( map[sc[right++]]-->=1) count--;
            }

        }
        return result;
    }
}

https://leetcode.com/problems/longest-repeating-character-replacement/
也是一道滑動窗口的題，在解決諸如substring這類問題時，不妨嘗試想一想滑動窗口。