算法系列（七）滑动窗口

[TOC]

76.最小覆盖子串

• 解题要点：如何移动窗口的左右边界？何时更新result？

  public String minWindow(String s, String t) {
    HashMap<Character, Integer> need = new HashMap<>();
    for (char c : t.toCharArray()) {
      need.put(c, need.getOrDefault(c, 0) + 1);
    }
    HashMap<Character, Integer> window = new HashMap<>();
    int matchCount = 0;
    int left = 0, right = 0;
    int start = 0;
    int minLen = Integer.MAX_VALUE;
    while (right < s.length()) {
      char r = s.charAt(right);
      right++;
      if (need.containsKey(r)) {
        window.put(r, window.getOrDefault(r, 0) + 1);
        if (window.get(r).equals(need.get(r))) {
          matchCount++;
        }
      }
      while (matchCount == need.keySet().size()) {
        if (matchCount == need.keySet().size() && minLen > right - left) {
          start = left;
          minLen = right - left;
        }
        char l = s.charAt(left);
        left++;
        if (need.containsKey(l)) {
          if (window.get(l).equals(need.get(l))) {
            matchCount--;
          }
          window.put(l, window.getOrDefault(l, 0) - 1);
        }
      }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
  }
  

567.字符串的排列

• 滑动窗口应用，注意左边界移动的终止条件

  public boolean checkInclusion(String s1, String s2) {
      int[] need = new int[26];
      int s1CharCount = 0;
      for (char c : s1.toCharArray()) {
          if (need[c - 'a'] == 0) {
              s1CharCount++;
          }
          need[c - 'a']++;
      }
      int left = 0, right = 0;
      int validCount = 0;
      int[] window = new int[26];
      while (right < s2.length()) {
          char r = s2.charAt(right);
          right++;
          if (need[r - 'a'] != 0) {
              window[r - 'a']++;
              if (need[r - 'a'] == window[r - 'a']) {
                  validCount++;
              }
          }
          while (right - left >= s1.length()) {
              if (validCount == s1CharCount && right - left == s1.length()) {
                  return true;
              }
              char l = s2.charAt(left);
              left++;
              if (need[l - 'a'] != 0) {
                  if (need[l - 'a'] == window[l - 'a']) {
                      validCount--;
                  }
                  window[l - 'a']--;
              }
          }
      }
      return false;
  }
  

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

此题与 567. 字符串的排列 解法一致。

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

• 解题要点：关键点在于左右指针的移动，通过HashMap存储访问过元素的下标。

  def lengthOfLongestSubstring(self, s: str) -> int:
    indexDict = {}
    left = 0 
    right = 0
    maxLen = 0
    while right < len(s): 
      curr = s[right]
      right += 1
      if indexDict.get(curr) is not None:
        left = max(left, indexDict.get(curr))
      indexDict[curr] = right
      maxLen = max(maxLen, right - left)
      return maxLen