[type]滑动窗口

[Alice52]

滑动窗口

1. 求满足某种条件的最短或最长子数组[子串]

2. 使用场景

   • 最小摘要
   • sum大于target的最短子数组
   • 最长的无重复字符的子串
   • 最长的最多有k个不同字符的子串

3. 步骤

   • 确定在谁身上滑动
   • 确定类型: 定长的窗口 || 不定长的窗口{最大/小/长/短}
   • 构建6个变量
     1. Map: need{短字符串}
     2. Map: window{窗口内的满足条件的值}
     3. valid: 窗口内满足条件的值的个数: 与need一起
     4. left/right: 窗口的两边
     5. 存放结果的变量

4. 模板0

   Map<Character, Integer> window = new HashMap<>();
   
   int res = 0;
   int left = 0, right = 0;
   while (right < s.length()) {
       char c = s.charAt(right);
       right++;
       window.put(c, window.getOrDefault(c, 0) + 1);
   
       // 收缩 left 边界
       while (window.get(c) > 1) {
           char removed = s.charAt(left);
           left++;
           window.put(removed, window.getOrDefault(removed, 0) - 1);
       }
   
       res = Math.max(res, right - left);
   }

5. 模板1-固定长度窗口

   // 固定长度窗口: 窗口收缩靠的是左右边界值 和 t.length()
   void slidingWindow(String s, String t) {
       HashMap<Character, Integer> window = new HashMap<>();
       HashMap<Character, Integer> need = new HashMap<>();
       for (int i = 0; i < t.length(); i++) {
           need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
       }
   
       // TODO: result
   
       int left = 0, right = 0;
       int valid = 0;
       while (right < s.length()) {
           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 (right - left >= t.length()) {
               // valid: 判断收割结果
               if (valid == need.keySet().size()) {
                   // TODO: 收割结果
               }
   
               // d 是将移出窗口的字符
               char removed = s.charAt(left);
               left++;
               // 进行窗口内数据的一系列更新
               if (need.containsKey(removed)) {
                   if (window.get(removed).equals(need.get(removed))) {
                       valid--;
                   }
                   window.put(removed, window.getOrDefault(removed, 0) - 1);
               }
           }
       }
   }

6. 模板2-不固定长度窗口

   // 不固定长度窗口: 窗口收缩靠 valid 与 need.size()
   void slidingWindow(String s, String t) {
       // part-1: init template
       Map<Character, Integer> need = new HashMap<>();
       Map<Character, Integer> window = new HashMap<>();
       for (int i = 0; i < t.length(); i++) {
           need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
       }
   
       // TODO: result variable
       int valid = 0;
       int left = 0, right = 0;
       while (right < s.length()) {
           // part-2-1: move right 
           char c = s.charAt(right);
           right++;
           // part-2-2: add value to window and valid
           if (need.containsKey(c)) {
               window.put(c, window.getOrDefault(c, 0) + 1);
               if (window.get(c).equals(need.get(c))) {
                   valid++;
               }
           }
   
           // part-3: move left continue
           // 收缩 left 边界
           while (valid == need.keySet().size()) {
               // TODO: 收割结果
               // part-4: collect result
   
               // part-5-1: move left 
               char removed = s.charAt(left);
               left++;
               // part-2-2: remove value from window and valid
               if (need.containsKey(removed)) {
                   if (window.get(removed).equals((need.get(removed)))) {
                       valid--;
                   }
                   window.put(removed, window.getOrDefault(removed, 0) - 1);
               }
           }
       }
   }

list

1. 3-无重复字符的最长子串
   • 一个字符串的模板题: 只需要 left, right, windows, res 四个变量
2. 567-字符串的排列
   • 两个字符串的定长的模板题: need, windows, left, right, valid, res
3. 438-到字符串中所有字母异位词
   • 两个字符串的定长的模板题: need, windows, left, right, valid, res{left}
4. 76-最小覆盖子串
   • 两个字符串的不定长的模板题: need, windows, left, right, valid, res