滑动窗口首先按照类型分，可以分为定长窗口和变长窗口。
定长窗口也就是说题目给出来的时候，你知道这个窗口的长度是固定的，一般会要求你返回每个这样的窗口。我们只需要处理I,J 2根指针同时向后移一位。然后每次的位移过程里做的事是需要技巧的。

定长窗口典型题目有

Given an integer array A and a sliding window of size K, find the maximum value of each window as it slides from left to right.

Assumptions

The given array is not null and is not empty

K >= 1, K <= A.length

Examples

A = {1, 2, 3, 2, 4, 2, 1}, K = 3, the windows are {{1,2,3}, {2,3,2}, {3,2,4}, {2,4,2}, {4,2,1}},

and the maximum values of each K-sized sliding window are [3, 3, 4, 4, 4]

或者
Find all occurrence of anagrams of a given string s in a given string l. Return the list of starting indices.

Assumptions

s is not null or empty.
l is not null.
Examples

l = "abcbac", s = "ab", return [0, 3] since the substring with length 2 starting from index 0/3 are all anagrams of "ab" ("ab", "ba").

上面第一个题目的技巧是维护一个单调DEQUE，我们需要思考的是一个窗口里的最大值取决于什么，有哪些元素对最大值是完全没有贡献的。我们发现，一个位置靠前并且比这个窗口里后面的值还小的那个数 是不可能对之后窗口的最大值产生价值。所以我们可以之前把它丢掉。根据这个原则。我们DEQUE的最左端是该窗口的最大值。同时DEQUE维持了单调递减的特性。后面继续保持这个特性即可。

public List<Integer> maxWindows(int[] array, int k) {
    // Write your solution here
    Deque<Integer> dq = new ArrayDeque<>();
    if (k > array.length) k = array.length;
    for (int i = 0; i < k; i++) {
      while (!dq.isEmpty() && array[i] > dq.peekLast()) dq.pollLast();
      dq.offerLast(array[i]);
    }
    List<Integer> res = new ArrayList<>();
    res.add(dq.peekFirst());
    for (int i = k; i < array.length; i++) {
      if (array[i - k] == dq.peekFirst()) dq.pollFirst();
      while (!dq.isEmpty() && array[i] > dq.peekLast()) dq.pollLast();
      dq.offerLast(array[i]);
      res.add(dq.peekFirst());
    }
    return res;
  }

第二道题，就是要看什么时候需要去更新CNT变量，只有当S里的字符的计数是正的时候，删除的时候需要CNT--。是》=0的时候，增加的时候需要CNT++。 因为无用的字符，前面没有初始化。所以增加的时候那时的值必然为负数。

public List<Integer> allAnagrams(String sh, String lo) {
    int i = 0;
    int[] map = new int[256];
    for (char c : sh.toCharArray()) map[c]++;
    int cnt = sh.length();
    List<Integer> res = new ArrayList<>();
    if (lo.length() < sh.length()) return res;
    int j = 0;
    while (j < sh.length()) {
     if (map[lo.charAt(j++)]-- > 0){
       cnt--;
     }
    }
    if (cnt == 0) res.add(i);
    while (j < lo.length()) {
      if (map[lo.charAt(i++)]++ >= 0){
       cnt++;
      }
      if (map[lo.charAt(j++)]-- > 0) {
        cnt--;
      }
      if (cnt == 0) res.add(i);
    }
    
    return res;
  }

其他定长窗口
Given a string containing only 'A', 'B', 'C', 'D', return the number of occurrences of substring which has length 4 and includes all of the characters from 'A', 'B', 'C', 'D' with in descending sorted order.

Assumptions:

The given string is not null and has length of >= 4.
In the output, if two substrings have the same frequency, then they should be sorted by the their natural order.
Examples:

“ABCDABCDD”, --> {"ABCD" : 2, "BCDA" : 1, "CDAB" : 1, "DABC" : 1}

/**
 * public class Frequency {
 *   public String str;
 *   public int freq;
 *   public Frequency(String str, int freq) {
 *     this.str = str;
 *     this.freq = freq;
 *   }
 * }
 */
public class Solution {
  public List<Frequency> frequency(String input) {
    Map<String,Integer> map = new HashMap<>();
    int[] m = new int[4];
    int i = 0;
    int cnt = 0;
    char[] cs = input.toCharArray();
    for (; i < 4; i++) {
      if(m[cs[i] - 'A']++ == 0) cnt++;
    }
    for (; i <= cs.length; i++) {
      if (cnt == 4) {
        String key = input.substring(i - 4, i);
        map.putIfAbsent(key,0);
        map.put(key, map.get(key) + 1);
      }
      if (i == cs.length) break;
      if(--m[cs[i - 4] - 'A'] == 0) cnt--;
      if(m[cs[i] - 'A']++ == 0) cnt++;
    }
    List<Frequency> res = new ArrayList<Frequency>();
    for (String key : map.keySet()) {
      res.add(new Frequency(key, map.get(key)));
    }
    Collections.sort(res, new Comparator<Frequency> () {
      public int compare(Frequency a, Frequency b) {
        if (a.freq == b.freq) return a.str.compareTo(b.str);
        return b.freq - a.freq;
      }
    });
              
    return res;
  }
}

下面我们来看变长的窗口。

变长窗口最让人头疼的问题是很容易，移着移着指针就混乱了，一跑代码不是有错误，就是INDEX越界。所以基于这个问题，我设计了一套针对滑动窗口的不变量来避免写代码的时候发生想不清楚而引入BUG或者死循环指针越界的问题。

变长窗口会有2类 一般会让你找最长的窗口，或者最短的窗口。所以道题滑动变长窗口题，可以仅仅改一个单词，就让题目变化。
比如：
Given a string, return the longest contiguous substring that contains exactly k type of characters.

Return null if there does not exist such substring.

Assumptions:

The given string is not null.
k >= 0.
Examples:

input = "aabcc", k = 3, output = "aabcc".
input = "aabcccc", k = 2, output = "bcccc".

变化：
Given a string, return the shortest contiguous substring that contains exactly k type of characters.

Return an empty string if there does not exist such substring.

Assumptions:

The given string is not null.
k >= 0.
Examples:

input = "aabcc", k = 3, output = "abc".
input = "aabbbcccc", k = 3, output = "abbbc".
input = "aabcc", k = 4, output = "".

如果求最长，也就是在窗口满足条件的时候，移动后面一个（J）指针。
如果求最短，则相反，当窗口满足条件时，移动前一个（I）指针。

根据上述思想，我们要思考I,J的物理意义
我个人一般喜欢定义窗口区间为前闭，后开
这样给I,J 赋初始值的时候可以为0,0

那么循环退出一般是J 》 ARRAY.LENGTH的时候
所以我一般会用如下框架解决滑动窗口。
先看找最小窗口

        int min = Integer.MAX_VALUE;
        int i = 0, j = 0;
        while (j <= array.length) {
            if (满足条件) {
                min = Math.min(min, j - i);
                updateState(i++)
            } else {
                if (j == array.length) break;
                updateState(j++)
            }
        }
        return min;

最长窗口

        int max= 0;
        int i = 0, j = 0;
        while (j <= array.length) {
            if (窗口需要增大) {
                if (满足条件）
                    max= Math.max(max, j - i);
                if (j == array.length) break;
                updateState(j++)
            } else {
                updateState(i++)
            }
        }
        return max;

根据这2个设计思路，我们可以很轻松的解决上面2个问题。

public String shortest(String input, int k) {
    char[] cs = input.toCharArray();
    int min = cs.length;
    int s = 0, e = 0;
    int i = 0, j = 0;
    int[] map = new int[256];
    if (k == 0) return "";
    while (j <= cs.length) {
      if (k == 0) {
        if (j - i < min) {
          min = j - i;
          s = i;
          e = j;
        }
        if (++map[cs[i++]] == 0) k++;
      } else {
        if (j == cs.length) break;
        if (map[cs[j++]]-- == 0) k--;
      }
    }
    return input.substring(s,e);
  }

最长

public String longest(String input, int k) {
    char[] cs = input.toCharArray();
    int max = 0;
    int s = 0, e = 0;
    int i = 0, j = 0;
    int[] map = new int[256];
    if (k == 0) return "";
    while (j <= cs.length) {
      if (k >= 0) {
        if (k == 0 && j - i > max) {
          max = j - i;
          s = i;
          e = j;
        }
        if (j == cs.length) break;
        
        if (map[cs[j++]]-- == 0) k--;
        
      } else {
        if (++map[cs[i++]] == 0) k++;
      }
    }
    return s == e ? null : input.substring(s,e);
  }

我们再来看几道别的题，是不是都差不多了。

Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T

Input: S = “ADOBECODEBANC”

      T = “ABC”

Output: “BANC”

public String minWindow(String source, String target) {
    int[] map = new int[256];
    for (char c : target.toCharArray()) {
      map[c]++;
    }
    int i = 0, j = 0;
    char[] cs = source.toCharArray();
    int cnt = target.length();
    if (cnt == 0) return target;
    int min = source.length();
    int s = 0, e = 0;
    while (j <= cs.length) {
      if (cnt == 0) {
        if (j - i < min) {
          min = j - i;
          s = i;
          e = j;
        }
        if (map[cs[i++]]++ == 0) cnt++;
      } else {
        if (j == cs.length) break;
        if (map[cs[j++]]-- > 0) cnt--;
      }
    }
    return source.substring(s,e);
  }

Smallest Substring Containing All Characters Of Another String

Given two strings s1 and s2, find the shortest substring in s1 containing all characters in s2.

If there does not exist such substring in s1, return an empty string.

Assumptions:

s1 and s2 are not null or empty.
Examples:

s1= “The given test strings”

s2: “itsst”

Output string: “st stri”

public String smallest(String s1, String s2) {
    int[] map = new int[256];
    for (char c : s2.toCharArray()) map[c]++;
    int cnt = s2.length();
    int i = 0, j = 0;
    char[] cs = s1.toCharArray();
    int min = Integer.MAX_VALUE, s = 0, e = 0;
    while (j <= cs.length) {
      if (cnt == 0) {
        if (j - i < min) {
          min = j - i;
          s = i;
          e = j;
        }
        if (++map[cs[i++]] > 0) cnt++;
      } else{
        if (j == cs.length) break;
        if (map[cs[j++]]-- > 0) cnt--;
      }
    }
    return s1.substring(s,e);
  }

Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

public int minSubArrayLen(int num, int[] nums) {
    int i = 0, j = 0, min = Integer.MAX_VALUE;
    if (num <= 0) return 0;
    while (j <= nums.length) {
      if (num <= 0) {
        min = Math.min(min, j - i);
        num += nums[i++];
      } else {
        if (j == nums.length) break;
        num -= nums[j++];
      }
    }
    return min == Integer.MAX_VALUE ? 0 : min;
  }

最长的变长窗口

Longest Substring with At Most Two Distinct Characters

Given a string, find the the longest substring T that contains at most 2 distinct characters.

For example, Given s = “eceba”, T is "ece"

public int lengthOfLongestSubstringTwoDistinct(String input) {
        char[] cs = input.toCharArray();
        int i = 0, j = 0;
        int k = 2;
        int[] map = new int[256];
        int max = 0;
        while (j <= cs.length) {
            if (k >= 0) {
              max = Math.max(max, j - i);
              if (j == cs.length) break;
              if (map[cs[j++]]++ == 0) k--;
            } else {
              if (--map[cs[i++]] == 0) k++;
            } 
        }
        return max;
  }