滑动窗口最经典的题目

主要要思考4个问题

  • 当移动right时，也就是加入字符，需要更新哪些数据
  • 什么条件下，窗口应该暂停扩大，开始移动left窗口
  • 当移动left缩小窗口时，应该更新哪些数据
  • 我们要的结果是在扩大窗口时还是缩小窗口时进行更新

    2与4其实是对称的，

  1. public String minWindow(String s, String t) {
  2.     Map<Character, Integer> needs = new HashMap<>();
  3.     Map<Character, Integer> windows = new HashMap<>();
  5.     int left = 0;
  6.     int right = 0;
  8.     int valid = 0;
  9.     int start = 0;
  10.     int len = Integer.MAX_VALUE;
  12.     char[] tC = t.toCharArray();
  13.     char[] sC = s.toCharArray();
  14.     for (char c : tC) {
  15.         needs.put(c, needs.getOrDefault(c, 0) + 1);
  16.     }
  18.     while (right < s.length()) {
  19.         char c = sC[right];
  20.         right++;
  21.         if (needs.containsKey(c)) {
  22.             windows.put(c, windows.getOrDefault(c, 0) + 1);
  23.             if (windows.getOrDefault(c, 0).equals(needs.get(c))) {
  24.                 valid++;
  25.             }
  26.         }
  29.         while (valid == needs.size()) {
  30.             if (right - left < len) {
  31.                 start = left;
  32.                 len = right - left;
  33.             }
  35.             char d = sC[left];
  36.             left++;
  37.             if (needs.containsKey(d)) {
  38.                 if (windows.getOrDefault(d, 0).equals(needs.get(d))) {
  39.                     valid--;
  40.                 }
  41.                 windows.put(d, windows.getOrDefault(d, 1) - 1);
  42.             }
  43.         }
  44.     }
  45.     return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
  46. }

类似题目：

567. 字符串的排列

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

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