[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.字符串的排列

• 滑動窗口應(yīng)用赴邻，注意左邊界移動的終止條件

  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.無重復(fù)字符的最長子串

• 解題要點：關(guān)鍵點在于左右指針的移動紊选，通過HashMap存儲訪問過元素的下標(biāo)。

  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