摘要：滑動窗口問題經(jīng)常使用快慢指針的區(qū)域為滑動窗口已經(jīng)探索過的區(qū)域的區(qū)域為滑動窗口正在探索的區(qū)域為待探索的區(qū)域的問題主要分為和當(dāng)快指針增加的時候慢指針必須增加快指針增加，慢指針不一定變化使用滑動窗口可以線性時間解決問題而且可以減少空間消耗要求

滑動窗口(Sliding Window)問題經(jīng)常使用快慢指針(slow, fast pointer)
[0, slow)?的區(qū)域為滑動窗口已經(jīng)探索過的區(qū)域
[slow, fast]的區(qū)域為滑動窗口正在探索的區(qū)域
(fast, end of array)為待探索的區(qū)域

Sliding Window的問題主要分為:
fixed size sliding window 和 dynamic size sliding window

fixed size sliding window: 當(dāng)快指針增加的時候慢指針必須增加
non-fixed size sliding window: 快指針增加，慢指針不一定變化

使用滑動窗口可以線性時間解決問題而且可以減少空間消耗

Fixed Length Sliding Window:
1.Strstr:
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Input: haystack = "hello", needle = "ll"
Output: 2
要求找到短字符串在的起始位置在長字符串中的位置
所以只需要保持一個fixed sliding window的長度為短字符串的長度然后掃長字符串來尋找起始位置

   class Solution{
       public int strStr(String long, String short) {
           //sanity check
            if(long == null || short == null) return -1;
            int i = 0;
            int j = needle.length();
            while(i <= haystack.length() - needle.length() && j <= haystack.length()) {
                if(haystack.substring(i, j).equals(needle)) {
                    return i;
                }
                i++;
                j++;
            }
            return -1;
         }
    }

2.Repeated DNA Sequennce
All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.
Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
Given s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT",
Return:
["AAAAACCCCC", "CCCCCAAAAA"]
這道題給一個堿基序列，要求我們返回在given的堿基序列中重復(fù)的堿基序列
所以這道題我們可以用一個定長的滑動窗口，每次去match在given的堿基序列中任意的position從而返回所用出現(xiàn)過的重復(fù)的堿基序列，可以用一個HashSet的數(shù)據(jù)結(jié)構(gòu)來判斷是否已經(jīng)檢查過已經(jīng)出現(xiàn)的序列

class Solution{
    public List repeatedDNASequence(String s) {
        HashSet window = new HashSet();
        HashSet repeated = new HashSet();
        
        for(int i = 0; i < s.length() - 9; i++) {
            if(!window.add(s.substring(i, i + 10))) {
                repeated.add(s.substring(i, i + 10));
            }
        }
        return new ArrayList(repeated);
    }
}

Non-fixed Size Sliding-Window
3.find all anagrams of shortString in longString
Given a string s and a non-empty string p, find all the start indices of p"s anagrams in s.Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.The order of output does not matter.
Example 1:
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".
Example 2:
Input: s: "abab" p: "ab"
Output: [0, 1, 2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".
這道題是尋找input長字符串中所有出現(xiàn)子串的起始字母在長字符串中的位置
因為我們需要找到長字符串中所有match子串的字符串并且返回需要match的字串中第一個字母在長字符串中的位置，所以需要用一個動態(tài)的滑動窗口慢指針在match的子字符串的第一個字母在長字符串中的位置，快指針在最后一個match的字母在長字符串中的位置， 然后需要一個hashmap來記錄每個字母出現(xiàn)的頻率，利用length來teminate

class Solution{
    public List findAnagrams(String s, String p) {
        //sanity check
        List res = new ArrayList();
        //count the frequency of each appeared character
        Map map = new HashMap();
        for(char c : p.toCharArray()) {
            map.put(c, map.getOrDefault(0, c) + 1);
        }
        int fast = 0;
        int slow = 0;
        int count = map.size();//記錄所有出現(xiàn)過字符的頻率
        //update fast pointer
        while(fast < s.length()) {
            char c = s.charAt(fast);
            if(map.containsKey(s.charAt(fast)) {
                map.put(c, map.get(fast) - 1);
                if(map.get(c) == 0) count--;
            }
            fast++;
            //update slow pointer
            while(count == 0) {
                char temp = s.charAt(slow);
                if(map.containsKey(temp)) {
                    map.put(temp, map.get(temp) + 1));
                    if(map.get(temp) > 0) count++;
                }
                //store res;
                if(fast - slow == p.length()) {
                    res.add(slow);
                }
                slow++;
            }
       }
       return res;
    }
}

4.Maximum Value of size K subarray
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
這題要求找到given數(shù)組中任意定長的滑動窗口中數(shù)的最大值，因此需要考慮一個數(shù)據(jù)結(jié)構(gòu)可以在移動的滑動窗口中找到最大值，因此有幾種想法：
1.在定長的滑動窗口里維持一個最大堆，因此我們可以用constant時間去找到最大值，但是考慮到每次heapify的時間需要O(logn)，所以找到k個最大值需要花費O(klogn)的時間
2.還是同樣在定長的滑動窗口里維持一個treeset，但是考慮到每次在treeset中添加或者刪除元素需要花費O(logn)的時間，所以是否存在一個數(shù)據(jù)結(jié)構(gòu)可以在線性時間內(nèi)得到定長滑動窗口里的最大值？
3.因而，想到了雙端隊列(Deque),可以維持一個遞增的雙端隊列
EX:[|1, 4|, 5, 3, 9], k = 3
我們先將k-1個元素放入隊列:|2|
然后從第k個元素開始，一次加入新元素并刪除舊元素，并且保持滑動窗口的size不變
[|1, 4, 5|, 3, 9], Deque: 5, Output: [5];
[1, |4, 5, 3|, 9], Deque: 5, 5, Output: [5, 5];
[1, 4, |5, 3, 9|], Deque: 8, Output: [5, 5, 8];
因為對于每個數(shù)組中的元素只掃描一次，所以總體時間在deque操作中也近似于線性，所以總運行時間：O(n)(amortized), 空間復(fù)雜度:O(1)

class slidingWindowMax{
    public void inQueue(Deque deque, int k) {
        while(!deque.isEmpty() && deque.peekLast() < k) {
            deque.pollLast();
        }
        deque.offerLast(num);
    }
    public void outQueue(Deque deque, int k) {
           if(deque.peekFirst() == k) {
               deque.pollFirst();
           }
    }
    public int[] maxSlidingWindow(int[] nums, int k) {
        List ans = new ArrayList();
        Deque deque = new ArrayDeque();
        
        if(nums == null || nums.length == 0) {
            return new int[]{};
        }
        
        for(int i = 0; i < k - 1; i++) {
            inQueue(deque, nums[i]);
        }
        
        for(int i = k - 1; i < nums.length; i++) {
            inQueue(deque, nums[i]);
            res.add(deque.peekFirst());
            outQueue(deque, nums[i - k + 1]);//delete old element
         }
         int[] res = new int[ans.size()];
         int h = 0;
         for(int num : res) {
             res[h++] = num;
         }
         return res;
    }
}