一.滑动窗口模板

1.思路

  1. 源串sourceStr，匹配串targetStr
  2. sourceMap保存窗口中的字符和出现次数，targetMap保存匹配串的字符和出现次数
  3. left、right指针，[left,right]为窗口大小，右移动right扩张窗口将扫描的元素放入sourceMap寻找可能的解，左移动left缩小窗口寻找有效的解（真正的解）
  4. valid变量，表示窗口中的符合条件的字符的个数，当窗口中有一个字符从不符合条件到符合题目给出的条件时valid加1，当窗口中有一个字符从符合条件到不符合题目给出的条件时valid减1，比如窗口中某个字符c出现次数从小于到等于targetMap.get(c)时valid++，当窗口中某个字符c出现次数从到等于到小于targetMap.get(c)时valid—

代码模板：

  1. // 扫描目标序列targetStr初始化targetMap
  2. for(int i=0;i<pLen;i++){
  3.   char c = p.charAt(i);
  4.   targetMap.put(c, targetMap.getOrDefault(c, 0)+1);
  5. }
  6. int left=0,right=0,valid=0;
  7. int sourceLen = sourceStr.length();
  8. // 右移动right,将right加入sourceMap寻找可能的解,在适当时候给valid加1
  9. while(right<sourceLen){
  10.     char cRight = sourceSt.charAt(right);
  11.     sourceMap.put(cRight, sourceMap.getOrDefault(cRight, 0)+1);
  12.   // 当窗口中有一个字符从不符合条件到符合题目给出的条件时valid加1
  13.   if(sMap.get(cRight).equals(pMap.get(cRight))){
  14.       valid++;
  15.   }
  16.   // 当valid大小为targetStr所有字符种类时,不断缩小left不断寻找真正的解
  17.   while (valid==pMap.size()){
  18.       // 根据题目条件
  19.     if(judge()){
  20.       // 找到一个解
  21.     }
  23.     char cLeft = s.charAt(left);
  24.        // 当窗口中有一个字符从符合条件到不符合题目给出的条件时valid减1
  25.     if(sourceMap.get(cLeft).equals(targetMap.get(cLeft))){
  26.             valid--;
  27.     }
  28.     // 从窗口中删除left位置字符
  29.     sourceMap.put(cLeft, sourceMa.getOrDefault(cLeft, 0)-1);
  30.     // 若left位置字符不再出现在窗口中,则在sourceMap中移除
  31.     if(sMap.get(cLeft)==0){
  32.         sourceMap.remove(cLeft);
  33.     }
  34.     // 右移动left
  35.     left++;
  36.     }
  37.     // 右移动right
  38.     right++;
  39. }

2.可用模板做的题

LeetCode-438. 找到字符串中所有字母异位词
LeetCode-76.最小覆盖子串-困难
LeetCode-3.无重复字符的最长子串-中等

二.滑动窗口题目

LeetCode-3.无重复字符的最长子串-中等

描述：
思路： “连续子序列”，使用双指针滑动窗口

  1.     // 窗口left,right从0开始,首先扩大窗口right右移动, 每次移动都将{val:index}存放进入map中
  2.     // 当right右移的新index对应的字符已经在map中存在时, 更新left = Math.max(left, map.get(val)+1);
  3.     public int lengthOfLongestSubstring(String s) {
  4.         if(s.length()==0){
  5.             return 0;
  6.         }
  7.         int maxLen = 1;
  8.         int left = 0, right = 0, n = s.length();
  9.         Map<Character, Integer> map = new HashMap<>();
  10.         while(right<n){
  11.             char rightChar = s.charAt(right);
  12.             if(map.containsKey(rightChar)){
  13.                 left = Math.max(left, map.get(rightChar)+1);
  14.             }
  15.             // 每次都计算最大无重复子串长度
  16.             maxLen = Math.max(maxLen, right-left+1);
  17.             map.put(rightChar, right);
  18.             right++;
  19.         }
  20.         return maxLen;
  21.     }

LeetCode-76.最小覆盖子串-困难

LeetCode-209. 长度最小的子数组-中等

描述：给定一个含有 n 个正整数的数组和一个正整数 target ,找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
思路：

    // 连续子序列,滑动窗口
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, right = 0, n = nums.length;
        int sum = 0, minLen = Integer.MAX_VALUE;
        // 窗口扩大
        while(right<n){
            sum += nums[right];
            // 窗口缩小
            while(sum>=target){
                minLen = Math.min(minLen, right-left+1);
                sum -= nums[left++];
            }
            right++;
        }
        return minLen==Integer.MAX_VALUE?0:minLen;
    }

LeetCode-239.滑动窗口最大值-困难

LeetCode-395.至少有 K 个重复字符的最长子串-中等

描述：
思路：
（1）分治

（2）滑动窗口，时间O(N⋅∣Σ∣)，Σ为字符集，本题中字符串仅包含小写字母，因此∣Σ∣=26
枚举字符种类数目x, 子串的字符种类数目要在小于等于x的前提下满足每个出现的字符重复次数不小于k
维护窗口内的字符集种类数量 windowCharCount 、窗口内的频率大于等于k的字符种类数量 valid
characterSet[y] 表示字符集中y位置字符的出现次数
characterSet[y]从0到1时, windowCharCount加1; 从1到0时, windowCharCount减1
characterSet[y]从k-1到k时, valid加1; 从k到k-1时, valid减1

        // 连续子序列满足特定条件, 滑动窗口
    public int longestSubstring(String s, int k) {
        int maxLen = 0;
        // 最多有26种字符
        for(int i=0;i<=26;i++){
            int left = 0, right = 0, n = s.length();
            // characterSet[y]表示第y个字符出现频率
            int[] characterSet = new int[26];
            // 窗口内字符集种类数量
            int windowCharCount = 0;
            // valid表示窗口内频率大于等于k的字符数
            int valid = 0;
            while(right<n){
                int rightIndex = s.charAt(right) - 'a';
                characterSet[rightIndex]++;
                if(characterSet[rightIndex]==1){
                    windowCharCount++;
                }
                if(characterSet[rightIndex]==k){
                    valid++;
                }
                // 窗口内字符种类数量大于枚举的字符种类数量时, 缩小窗口(右移left)
                while(windowCharCount>i){
                    int leftIndex = s.charAt(left) - 'a';
                    characterSet[leftIndex]--;
                    if(characterSet[leftIndex] == 0){
                        windowCharCount--;
                    }
                    if(characterSet[leftIndex] == k-1){
                        valid--;
                    }
                    left++;
                }
                if(valid==windowCharCount){
                    maxLen = Math.max(maxLen, right - left + 1);
                }
                right++;
            }
        }
        return maxLen;
    }

LeetCode-424.替换后的最长重复字符-中等

描述：
思路：

LeetCode-438. 找到字符串中所有字母异位词-中等

描述：
思路：

LeetCode-480.滑动窗口中位数-困难

LeetCode-567.字符串的排列-中等

描述：
思路：

LeetCode-713. 乘积小于K的子数组-中等

描述：
思路：

LeetCode-763. 划分字母区间-中等

描述：
思路：

LeetCode-845. 数组中的最长山脉-中等

描述：
思路：

LeetCode-881. 救生艇-中等

描述：
思路：

LeetCode-904. 水果成篮-中等

LeetCode-978. 最长湍流子数组-中等

LeetCode-992. K 个不同整数的子数组-困难

LeetCode-1004. 最大连续1的个数 III-中等

LeetCode-1040. 移动石子直到连续 II-中等

LeetCode-1052. 爱生气的书店老板-中等

LeetCode-1208.尽可能使字符串相等-中等
LeetCode-1423.可获得的最大点数-中等
LeetCode-1438.绝对差不超过限制的最长连续子数组-中等
LeetCode-1456.定长子串中元音的最大数目-中等
LeetCode-1498.满足条件的子序列数目-中等
LeetCode-1499.满足不等式的最大值-困难
LeetCode-1658.将 x 减到 0 的最小操作数-中等
LeetCode-剑指 Offer 48.最长不含重复字符的子字符串-中等
LeetCode-剑指 Offer 59 - I.滑动窗口的最大值-困难
LeetCode-剑指 Offer 59 - II.队列的最大值-中等
LeetCode-面试题 17.18.最短超串-中等

参考：滑动窗口模板
labuladong的算法小抄