滑动窗口算法

76.最小覆盖子串

/* 滑动窗口算法框架 */
  void slidingWindow(String s, String t) {
      HashMap<Character, Integer> need, window;
      for (char c : t.toCharArray()) {
          need.put(c, need.getOrDefault(c, 0) + 1);
      }

      int left = 0, right = 0;
      int valid = 0;
      while (right < s.length()) {
          // c 是将移入窗口的字符
          char c = s.charAt(right);
          // 右移窗口
          right++;
          // 进行窗口内数据的一系列更新
      		...

          /*** debug 输出的位置 ***/
          System.out.printf("window: [%d, %d)\n", left, right);
          /********************/

          // 判断左侧窗口是否要收缩
          while (window needs shrink){
              // d 是将移出窗口的字符
              char d = s.charAt(left);
              // 左移窗口
              left++;
              // 进行窗口内数据的一系列更新
        		  ...
          }
      }

⏬⏬⏬

public String minWindow(String s, String t) {
       HashMap<Character, Integer> need = new HashMap<>();
       HashMap<Character, Integer> window = new HashMap<>();
       for (Character c : t.toCharArray()) {
           need.put(c, need.getOrDefault(c, 0) + 1);
       }
       int left = 0;
       int right = 0;
       //满足need条件的字符个数
       int vaild = 0;
       //记录最小覆盖子串的其实索引和长度
       int start = 0;
       int len = Integer.MAX_VALUE;
       while (right < s.length()) {
           //c是即将移入窗口的字符
           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))) {
                   vaild++;
               }
           }
           //判断左侧窗口是否需要收缩
           while (vaild == need.size()) {
               //更新最小覆盖子串
               if (right - left < len) {
                   start = left;
                   len = right - left;
               }
               //d是即将移除的字符
               char d = s.charAt(left);
               //左移窗口
               left++;
               //进行窗口内数据更新
               if (need.containsKey(d)) {
                   if (window.get(d).equals(need.get(d))) {
                       vaild--;
                   }
                   window.put(d, window.get(d) - 1);
               }
           }
       }
       //返回最小覆盖子串
       return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
   }