一、声明

1.非常感谢东哥（labuladong）分享了**滑动窗口算法框架**；
2.我在理解了东哥的思想后，用Java实现了滑动窗口算法框架，一来方便自己学习，二来方便一些Java小伙伴；
3.再次感谢互联网上的大佬们分享智慧结晶。

二、滑动窗口算法框架

滑动窗口：[left, right)

Map<Character, Integer> window = new HashMap<>();
int size = s.size();
int left = 0, right = 0;
while(right < size) {
	//增大窗口
	char c = s.charAt(right);
	right++;
	window.put(c, window.getOrDefault(c, 0) + 1);

	while(window needs shrink) {
		//缩小窗口
		char d = s.charAt(left);
		left++;
		window.put(d, window.get(d) - 1);
	}
}

要熟练使用上述框架，需要做到以下几点：
①适用于子串问题；
②什么时候缩小窗口取决于题意；
比如：题目要求子串不得有重复字符。那么当窗口扩大到包含重复字符时，就需要收缩窗口了。（见三、4）
③什么时候计算窗口大小（往往窗口大小就是答案）；
在window满足题目条件时，就可以计算窗口大小了，即res = right - left；；当然了，题目往往要求最优解，所以要更新res，寻求最优解。
④最好增加个预判：if(sizeS < sizeT) return res;，见三、3；

三、秒杀力扣题

0、前言

学习算法框架，就像学习咏春拳，切不可被拳法束缚住，而应该见招拆招。
而要想见招拆招，只能不断熟练拳法，毕竟孰能生巧嘛。

1、76. 最小覆盖子串

class Solution {
    public String minWindow(String s, String t) {
        // 需要包含t中的所有字符
        Map<Character, Integer> need = new HashMap<>();
        for(char c : t.toCharArray())
            need.put(c, need.getOrDefault(c, 0) + 1);

        //滑动窗口
        Map<Character, Integer> window = new HashMap<>();

        /*[left, right) 窗口大小：right - left; */
        int left = 0, right = 0; //初始时，窗口不包含任何元素
        int valid = 0;   //字符找齐了，valid++；
        int size = s.length();
        int minLen = size + 1; //包含t的子串不止1个，要求最小的。
        int start = 0;  //最优解的起点；
        while(right < size) {
            /* 右移动right，扩大窗口，寻找可行解 */
            char c = s.charAt(right);
            right++;
            if(need.containsKey(c)) {
                //如果是t中的字符，加入到window中
                window.put(c, window.getOrDefault(c, 0) + 1);
                //例:s->abbbce,t->be,第一次遍历到b时,valid加1,第二次遍历到b时,不会加1,因为
                //window.get(c).equals(need.get(c)) 为false,window.get(c)=2,need.get(c)=1
                if(window.get(c).equals(need.get(c)))
                    valid++;
            }

            /* 找到可行解后，右移动left，缩小窗口，进行优化 */
            int needSize = need.size();
            while(valid == needSize) {
                // 不断右移动left，直到valid != needSize
                c = s.charAt(left);
                left++;
                if(need.containsKey(c)) {
                    if(window.get(c).equals(need.get(c)))
                        valid--;
                    window.put(c, window.get(c) - 1);
                }
                /* 求最优解 [left - 1, right) */ 
                if(valid != needSize) {
                    if(right - left + 1 < minLen) {
                        start = left - 1;
                        minLen = right - left + 1;
                    }
                }
            }
        }
        return minLen == size + 1 ? "" : s.substring(start, start + minLen);
    }
}

注意：window.get(c).equals(need.get(c))，千万不能写成window.get(c) == need.get(c)!!!

2、567. 字符串的排列

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        Map<Character, Integer> need = new HashMap<>();
        for(char c : s1.toCharArray())
            need.put(c, need.getOrDefault(c, 0) + 1);
        Map<Character, Integer> window = new HashMap<>();
        int valid = 0;
        int left = 0, right = 0;
        int size1 = s2.length();
        while(right < size1) {
            char c = s2.charAt(right);
            right++;
            if(need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if(window.get(c).equals(need.get(c)))
                    valid++;
            }
            int needSize = need.size();
            int size2 = s1.length();
            while(valid == needSize) {
                if(right - left == size2)
                    return true;
                c = s2.charAt(left);
                left++;
                if(need.containsKey(c)) {
                    if(window.get(c).equals(need.get(c)))
                        valid--;
                    window.put(c, window.get(c) - 1);
                }
            }
        }
        return false;
    }
}

和76的代码基本一致，这就是滑动算法框架的魅力：一个模板秒杀一系列的题目（这实际上属于举一反三，毕竟得先理解题意，然后才知道如何应用模板）。

• 另一种实现方法

  class Solution {
  public boolean checkInclusion(String s1, String s2) {
  /* 运用滑动窗口算法思想*/
  //按照题目意思，此题的滑动窗口是固定大小；
  boolean res = false;
  int size1 = s1.length(), size2 = s2.length();
  int left = 0, right = left + size1;
  /* 对s1先排序 */
  char[] str1 = s1.toCharArray();
  Arrays.sort(str1);
  while(right <= size2) {
  char[] tmp = s2.substring(left, right).toCharArray();
  Arrays.sort(tmp);
  if(String.valueOf(tmp).equals(String.valueOf(str1))) {
  res = true;
  break;
  }
  left++;
  right = left + size1;
  }
  return res;
  }
  }

千万不要局限于模板，虽然上述代码性能不如滑动窗口算法框架，但是代码量少且容易实现。

3、438. 找到字符串中所有字母异位词

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res =  new ArrayList<>();
        int sizeS = s.length(), sizeT = p.length(); 
        if(sizeS < sizeT) return res;
        Map<Character, Integer> need = new HashMap<>();
        for(char c : p.toCharArray())
            need.put(c, need.getOrDefault(c, 0) + 1);
        int valid = 0;
        int needSize = need.size();
        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        
        while(right < sizeS) {
            char c = s.charAt(right);
            right++;
            if(need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if(window.get(c).equals(need.get(c)))
                    valid++;
            }

            while(valid == needSize) {
                if(right - left == sizeT) {
                    res.add(left);
                }
                c = s.charAt(left);
                left++;
                if(need.containsKey(c)) {
                    if(window.get(c).equals(need.get(c)))
                        valid--;
                    window.put(c, window.get(c) - 1);
                }
            }
        }
        return res;
    }
}

和567代码几乎一样。
另外，新增1个预判：if(sizeS < sizeT) return res;

4、3. 无重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        int size = s.length();
        int res = 0;
        while(right < size) {
            char c = s.charAt(right);
            window.put(c, window.getOrDefault(c, 0) + 1);
            right++;
            while(window.get(c) > 1) {
                /* 一旦出现了重复字符，就需要收缩窗口了 */
                char d = s.charAt(left);
                left++;
                window.put(d, window.get(d) - 1);
            }
            // [left, right) 窗口中没有重复字符
            res = Math.max(res, right - left);
        }
        return res;
    }
}

这题并不能生搬硬套华东算法框架，但仍旧是滑动窗口的思想。

/* 伪代码 */
while(right < size) {
	①统计字符，扩大窗口;(right++)
	②一旦重复，缩小窗口;(left++)
	③更新结果：res = Math.max(res, right - left);
}

5、485. 最大连续 1 的个数

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int left = 0, right = 0;
        int res = 0;
        while(right < nums.length) {
            //扩大窗口
            while(right < nums.length && nums[right] == 1) right++;
            //遇到了0或者已经超出边界，即不能再扩大了；
            res = Math.max(res, right - left);
            //缩小窗口
            right++; //跳过0
            left = right;
        }
        return res;
    }
}

虽然这道题看上去很像滑动窗口的题目，但是这种简单题反而用直觉的方法更好（不易出错，毕竟杀鸡焉用牛刀！）

6、后言

（1）最好不要奢望无脑套用框架刷算法题，而之所以学习些算法框架（或者说套路）是因为多积累一种解题思路往往多了一些机会去秒杀算法题。
（2）本文的滑动窗口算法框架在性能方面并不是最优的（毕竟套用框架省了脑力，多半会牺牲性能）。