我写了首诗，把滑动窗口算法变成了默写题 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：我写了首诗，把滑动窗口算法变成了默写题

评论礼仪 见这里，违者直接拉黑。

[lipku]

第2和第3题的
// 判断左侧窗口是否要收缩
while (right - left >= t.size()) {
这里判断条件应该有误，在right - left > t.size()时，此时得到的序列是不满足题目要求的

[piaomiaoaxin]

还是不太理解为什么这样是可以的 “ab” "acb"这样的情况 它是不return true的吗？？？
// 判断左侧窗口是否要收缩
while (right - left >= t.size()) {
// 在这里判断是否找到了合法的子串
if (valid == need.size())
return true;

[piaomiaoaxin]

明白了！！！自己打断点debug很清楚！！！

[bugcat9]

不会的，因为窗口大小只能是t.size()，保证了right-left不会大于t.size()

[zhuifeng-Q]

感觉这个改成if(right-left==t.size())更好理解

[kamisama2b]

对的，其实right每加一次，就要判断是否 right - left >= t.size() ，所以只可能出现 right -left == t.size()的情况。不会出现大于的情况。因此不会出现"ab","acb"返回true的

[Fightjiang]

是的，但是作者代码也没问题，只能说改成：if(right - left == t.size()) 就可以了，估计作者为了更好的模板话代码才那样写的叭。

[zhuifeng-Q]

想了半个小时，咱两想到一块了

[MessiahChen]

第二题第三题可以固定滑动窗口的大小为子串的长度来进行滑动吗？感觉可能更方便一点，作者这么写是不是也是为了模板的通用性？

[xluu233]

感谢大佬！！

[erdengk]

76题 ： Java 版本

 public String minWindow( String s, String t ) {
        String res = "";
        if ( t.length() > s.length() ) {
            return res;
        }

        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> window = new HashMap<>();

        for ( int i = 0; i < t.length(); i++ ) {
            char ch = t.charAt( i );
            need.put( ch, need.getOrDefault( ch, 0 ) + 1 );
        }
        int l = 0;
        int r = 0;
        int valid = 0;
        int len = Integer.MAX_VALUE;
        int start = 0;
        while ( r < s.length() ) {
            char ch = s.charAt( r );
            r++;
            if ( need.containsKey( ch ) ) {
                window.put( ch, window.getOrDefault( ch, 0 ) + 1 );
                if ( window.get( ch ).equals( need.get( ch ) ) ) {
                    valid++;
                }
            }
            // 判断左侧窗口是否要收缩
            while ( valid == need.size() ) {
                // 在这里更新最小覆盖子串
                if ( r - l < len ) {
                    start = l;
                    len = r - l;
                }
                // d 是将移出窗口的字符
                char d = s.charAt( l );
                // 左移窗口
                l++;
                // 进行窗口内数据的一系列更新
                if ( need.containsKey( d ) ) {
                    if ( window.get( d ).equals( need.get( d ) ) ) {
                        valid--;
                    }
                    window.put( d, window.get( d ) - 1 );
                }
            }
        }

        return len == Integer.MAX_VALUE ? "" : s.substring( start, start+len );
    }

[jianchengqiao]

@MessiahChen > 第二题第三题可以固定滑动窗口的大小为子串的长度来进行滑动吗？感觉可能更方便一点，作者这么写是不是也是为了模板的通用性？

我也发现了这一点，不过细想了一下，如果固定窗口大小，是不是窗口里的每个字符都得比较一次，这样的话时间复杂度就是O(s*t)，而东哥的做法只需要比较窗口长度，不用遍历窗口，时间复杂度是O(s)（最差也是O(2s)），不知道是不是这样。

[rongchenlin]

3道题目的Java版本在这里！

================ 76. 最小覆盖子串 ================
class Solution {
    public String minWindow(String s, String t) {
         // 记录t 以及 滑动窗口window中 字符与个数的映射关系
        HashMap<Character, Integer> window_map = new HashMap<>();
        HashMap<Character, Integer> t_map = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            char c1 = t.charAt(i);
            t_map.put(c1, t_map.getOrDefault(c1, 0) + 1);
        }
        // 双指针, 
        int left = 0;
        int right = 0;
        int count = 0;
        // 用于更新满足的窗口window的长度,如果是len一直是MAX_VALUE，说明没有满足的串
        int len = Integer.MAX_VALUE;
        // 用于记录window串的起始位置，则返回 s[start, len]
        int start = 0;

        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            // 只要c是t中出现的字符就更新
            if (t_map.containsKey(c)) {
                window_map.put(c, window_map.getOrDefault(c, 0) + 1);
                // 更新c字符出现的次数
                if (window_map.get(c).equals(t_map.get(c))) {
                    count++;
                }
            }
            // System.out.println(window_map); 
            // ----------------------------------
            // 收缩window的长度
            while (count == t_map.size()) {
                // 更新并记录window的长度,以及window的起始位置start
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }

                char d = s.charAt(left);
                left++;

                if (t_map.containsKey(d)) {
                    if (window_map.get(d).equals(t_map.get(d))) {
                        count--;
                    }
                    window_map.put(d, window_map.get(d) - 1);
                }
            }
        } 
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}
================ 438. 找到字符串中所有字母异位词 ================
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        // ========= 模板：定义相关数据结构，初始化工作============
        HashMap<Character, Integer> window_map = new HashMap<>();
        HashMap<Character, Integer> p_map = new HashMap<>();
        for (int i = 0; i < p.length(); i++){
            char c1 = p.charAt(i);
            p_map.put(c1, p_map.getOrDefault(c1, 0) + 1);
        }
        int left, right, count;
        left = right = count = 0;
        ArrayList<Integer> res = new ArrayList<>();

        // ================== 模板：开始滑动窗口=====================
        while (right < s.length()) {

            // =========== 模板：向右滑动窗口，装填满足的字符到map中==========
            char c = s.charAt(right);
            right++;
            if (p_map.containsKey(c)) {
                window_map.put(c, window_map.getOrDefault(c, 0) + 1);
                if (window_map.get(c).equals(p_map.get(c))) {
                    count++;
                }
            }

            // =========== 根据题意：此时“有可能”出现满足条件的解 ==========
            while (right - left == p.length()) {

                // ============= 根据题意：获取“真正”满足条件的解 =============
                if (count == p_map.size()){
                    res.add(left);
                }

                // ========== 模板：左指针向右滑动，寻找下一个可行解/优化已知解======
                char d = s.charAt(left);
                left++;
                if (p_map.containsKey(d)) {
                    if (window_map.get(d).equals(p_map.get(d))) {
                        count--;
                    }
                    window_map.put(d, window_map.getOrDefault(d, 0) - 1);
                } 
            }
        }
        return res;
    }
}
================ 567. 字符串的排列 ================
class Solution {
    public boolean checkInclusion(String p, String s) {
        // ========= 模板：定义相关数据结构，初始化工作============
        HashMap<Character, Integer> window_map = new HashMap<>();
        HashMap<Character, Integer> p_map = new HashMap<>();
        for (int i = 0; i < p.length(); i++){
            char c1 = p.charAt(i);
            p_map.put(c1, p_map.getOrDefault(c1, 0) + 1);
        }
        int left, right, count;
        left = right = count = 0;

        // ================== 模板：开始滑动窗口=====================
        while (right < s.length()) {

            // =========== 模板：向右滑动窗口，装填满足的字符到map中==========
            char c = s.charAt(right);
            right++;
            if (p_map.containsKey(c)) {
                window_map.put(c, window_map.getOrDefault(c, 0) + 1);
                if (window_map.get(c).equals(p_map.get(c))) {
                    count++;
                }
            }

            // =========== 根据题意：此时“有可能”出现满足条件的解 ==========
            while (right - left == p.length()) {

                // ============= 根据题意：获取“真正”满足条件的解 =============
                if (count == p_map.size()){
                    return true;
                }

                // ========== 模板：左指针向右滑动，寻找下一个可行解/优化已知解======
                char d = s.charAt(left);
                left++;
                if (p_map.containsKey(d)) {
                    if (window_map.get(d).equals(p_map.get(d))) {
                        count--;
                    }
                    window_map.put(d, window_map.getOrDefault(d, 0) - 1);
                } 
            }
        }
        return false;
    }
}

[labuladong]

@Hailei-J @tinainusa @InnovationFlash 你们确定不是自己写错了？我提交了一下都没有问题。

[Hailei-J]

@Hailei-J @tinainusa @InnovationFlash 你们确定不是自己写错了？我提交了一下都没有问题。

很神奇，用你的c++ code跑了下就没问题。
我是把你的code 用java写了一遍，最后需要把right++ 放在后面才pass。。。回头我再刷到这一章的时候在仔细研究下。若发现问题再回来讨论哈

[tangbo1430]

虽然速度效果一般，但是通过这个框架能记得比较牢，对于我这种菜鸡简直是福音，感谢大佬！！！

[labuladong]

速度一般是因为我为了模板的通用性直接用 hashmap 记录窗口中的数据。因为题目中说了只可能出现小写字母，所以可以用一个大小为 26 的数组代替 hashmap，这样就可以提升效率了。

[fornobugworld]

第2和第3题的 // 判断左侧窗口是否要收缩 while (right - left >= t.size()) { 这里判断条件应该有误，在right - left > t.size()时，此时得到的序列是不满足题目要求的

哈哈哈，这里的确是个思维误区，也不用二楼说的加个条件，我想了一天，还专门把代码跑了一遍发现没错。
问题出在这里窗口右边走一步，左边立即缩短。我们顺着之前的模板思考以为先是右边界一直走到包含子串再移动左边界，而这里左边界其实早就动起来了，一直保持着子串长度左右！

[jswxwxf]

js 版最小覆盖子串

function minWindow(s, t) {
  const needs = {},
    window = {};
  for (const c of t) {
    if (needs[c] === undefined) {
      needs[c] = 0;
    }
    needs[c]++;
    window[c] = 0;
  }
  const needsSize = Object.keys(needs).length;

  let left = 0,
    right = 0;
  let valid = 0;
  // 记录最小覆盖子串的起始索引及长度
  let start = 0,
    len = Infinity;
  while (right < s.length) {
    // c 是将移入窗口的字符
    const c = s[right];
    // 右移窗口
    right++;

    // 进行窗口内数据的一系列更新
    if (needs[c] !== undefined) {
      window[c]++;
      if (window[c] === needs[c]) {
        valid++;
      }
    }

    // 判断左侧窗口是否要收缩
    while (valid === needsSize) {
      // 在这里更新最小覆盖子串
      if (right - left < len) {
        start = left;
        len = right - left;
      }
      // d 是将移出窗口的字符
      const d = s[left];
      // 左移窗口
      left++;
      // 进行窗口内数据的一系列更新
      if (needs[d] !== undefined) {
        if (window[d] === needs[d]) valid--;
        window[d]--;
      }
    }
  }

  // 返回最小覆盖子串
  return len === Infinity ? "" : s.substr(start, len);
}

console.log(minWindow("aa", "aa"));

[jswxwxf]

js 版字符串排列

function checkInclusion(s1, s2) {
  const needs = {},
    window = {};
  for (const c of s1) {
    if (needs[c] === undefined) {
      needs[c] = 0;
    }
    needs[c]++;
    window[c] = 0;
  }
  const needsSize = Object.keys(needs).length;

  let left = 0,
    right = 0;
  let valid = 0;
  while (right < s2.length) {
    // c 是将移入窗口的字符
    const c = s2[right];
    // 右移窗口
    right++;

    // 进行窗口内数据的一系列更新
    if (needs[c] !== undefined) {
      window[c]++;
      if (window[c] === needs[c]) valid++;
    }

    // 判断左侧窗口是否要收缩
    while (right - left >= s1.length) {
      // 在这里判断是否找到了合法的子串
      if (valid === needsSize) return true;
      // d 是将移出窗口的字符
      const d = s2[left];
      // 左移窗口
      left++;

      // 进行窗口内数据的一系列更新
      if (needs[d] !== undefined) {
        if (window[d] === needs[d]) valid--;
        window[d]--;
      }
    }
  }
  return false;
}

console.log(checkInclusion("aba", "eidbaaooo"));

[jswxwxf]

js 最长无重复子串

function lengthOfLongestSubstring(s) {
  const window = {};
  for (const c of s) {
    window[c] = 0;
  }

  let left = 0,
    right = 0;
  let result = 0; // 记录结果
  while (right < s.length) {
    // c 是将移入窗口的字符
    const c = s[right];
    // 右移窗口
    right++;

    // 进行窗口内数据的一系列更新
    window[c]++;

    // 判断左侧窗口是否要收缩
    while (window[c] > 1) {
      // d 是将移出窗口的字符
      const d = s[left];
      // 左移窗口
      left++;

      // 进行窗口内数据的一系列更新
      window[d]--;
    }

    // 在这里更新答案
    result = Math.max(result, right - left);
  }

  return result;
}

console.log(lengthOfLongestSubstring("abcabcbb"));

[shadowclouds]

请教下，第二题和第三题，如果"ab"和"acb"为什么能够正确判断？我运行作者的代码运行正确，但是改成python就会出错。
会将acb错误和ab进行匹配

[weixueman]

这两个匹配不了啊，acb显然不包含ab的排列

[1272383808]

666

[LittleMaoer]

滑动窗口算法的代码框架的winodw.add(c)，window写错了

[labuladong]

感谢指出，已修正

[zhuifeng-Q]

大佬有个问题，我的理解valid 是不是解释为满足条件的字符种类的个数更合理一点

[Smelly-calf]

滑动窗口各个时刻window的状态
s=“ADOBECODEBANC”, t=“ABC”
right++
[0,0): window:{}
[0,1): {A:1} valid=1
[0,2): {A:1}
[0,3): {A:1}
[0,4): {A:1,B:1} valid=2
[0,5): {A:1,B:1}
[0,6): {A:1,B:1,C:1} valid=3：start=0, len=6

left++
[1,6): {A:0,B:1,C:1} valid=2

right++
[1,7): {A:0,B:1,C:1} valid=2
...
[1,10): {A:0,B:2,C:1} valid=2
[1,11): {A:1,B:2,C:1} valid=3

left++
[2,11): {A:1,B:2,C:1} valid=3
...
[4,11): {A:1,B:1,C:1} valid=3
...
[6,11): {A:1,B:1,C:0} valid=2
right++
[6,12): {A:1,B:1,C:0} valid=2
[6,13): {A:1,B:1,C:1} valid=3
left++
[7,13): {A:1,B:1,C:1} valid=3：start=7,len=5
...
[9,13): {A:1,B:1,C:1} valid=3：start=9,len=4
[10,13): {A:1,B:0,C:1} valid=2
right+1：right==s.size() 循环终止，结果：start=9, len=4

[Smelly-calf]

更正，最后没有right+1了，最后一次left移动到10:
[10,13): {A:1,B:0,C:1} valid=2
right==s.size() 循环终止，结果：start=9, len=4

[Crow77roket]

面试官：“....如果产品经理给你发了一长串需求....”
我：“滑动窗口！我会使用滑动窗口。”

两轮面试都出了子串相关的题目，滑动窗口真好用。

[QinYiXiao01]

我有一个问题，像第二题如果s1= i d e, s2 = e i d b a o o o, 我感觉文中的解法也是会返回true，因为没考虑字符串的排列，求解答，谢谢！

[QinYiXiao01]

或者说子串为啥可以是打乱顺序的

[Feezhen]

在最长无重复子串中遇到一个奇怪的问题。我用相同的代码，如果三个测试用例一起测试的话，在第二个就会出错，但是把第一个用例删掉的话，第二个用例就不会错。
代码如下：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> window;
int left=0, right = 0;
int ans;
printf("the value of ans is {%d}", ans);
// char repeat;
while(right < s.size()){
char c = s[right];
right++;
window[c]++;
if(window[c] == 1){
// repeat = Null;
int len = right - left;
if(len > ans){
ans = len;
}
}
else{
while(window[c] > 1){
char d = s[left];
left++;
window[d]--;
}
}

    }
    return ans;
}

};

[EchooWww]

第二题用int array的做法，需要多写一个helper method来比较两个int array，但是时间空间复杂度都更低

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        // Initialize 2 int arrays to store frequencies of characters in our target and our window
        int[] need = new int[26], window = new int[26];
        // Our target int array
        for(char c:s1.toCharArray()) need[c-'a']++;
        int left = 0, right = 0;
        // Check our window until the end of the array
        while(right < s2.length()) {
            char d = s2.charAt(right);
            right++;
            // If the character exists in our target, increase the corresponding element in our window
            if(need[d-'a']!=0) window[d-'a']++;
            // When the length of window equals our target string
            if(right - left == s1.length()) {
                // Check if the frequencies of chars in target and our window are equal
                if (areArraysEqual(need,window)) return true;
                // Shrink our window and update the frequencies in our window array
                char e = s2.charAt(left);
                left++;
                // If the char to be excluded is in our target, decrease the frequency
                if(need[e-'a']!=0) window[e-'a']--;
            }
        }
        return false;
    }
    // Helper method to judge if 2 int arrays are equal
    public boolean areArraysEqual(int[] arr1, int[] arr2) {
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
    return true;
    }   
}

[Feezhen]

非常感谢您的邮件。

[ningguo99]

最小覆盖子串里，我没用Integer.MAX_VALUE，而是用了如下的方式，在leetcode中显示266 / 267 testcases passed， 总有一个特别长的test case过不了，请帮我看看是出了什么问题，谢谢！

String currResult = s.substring(left, right);
if (result == "" || result.length() > currResult.length()) {
    result = currResult;
}

public String minWindow(String s, String t) {
        Map<Character, Integer> required = new HashMap<>();
        Map<Character, Integer> currentWindow = new HashMap<>();
        String result = "";
        for (int i = 0; i < t.length(); i++) {
            char curr = t.charAt(i);
            required.put(curr, required.getOrDefault(curr, 0) + 1);
        }
        int left = 0, right = 0;
        int numOfMeet = 0;
        while (right < s.length()) {
            char curr = s.charAt(right);
            right++;
            if (required.containsKey(curr)) {
                currentWindow.put(curr, currentWindow.getOrDefault(curr, 0) + 1);
                if (currentWindow.get(curr) == required.get(curr)) {
                    numOfMeet++;
                }
            }
            while (numOfMeet == required.size()) {
                String currResult = s.substring(left, right);
                if (result == "" || result.length() > currResult.length()) {
                    result = currResult;
                }
                char out = s.charAt(left);
                left++;
                if (currentWindow.containsKey(out)) {
                    
                    if (currentWindow.get(out) == required.get(out)) {
                        numOfMeet--;
                    }
                    currentWindow.put(out, currentWindow.get(out) - 1);
                }
            }
        }
        return result;
    }

[hanleilei]

非常感谢，我来一个424. Longest Repeating Character Replacement问题的题解，套用模板：

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        if not s:
            return 0

        # 记录每个字符出现的次数
        counter = collections.defaultdict(int)
        left = 0
        right = 0
        maxlen = 0
        res = 0

        while left <= right and right < len(s):
            c = s[right]
            right += 1
            counter[c] += 1
            maxlen = max(maxlen, counter[c])

            # 窗口长度减去最大字符出现次数小于 k，表示需要移动左指针
            while right - left - maxlen > k:
                d = s[left]
                left += 1
                counter[d] -= 1


            # 更新最大长度
            res = max(res, right - left)

        return res

希望能有所帮助

[syz6]

【76. 最小覆盖子串】代码分块，使代码与文中的算法思路对应更直接
【力扣测试通过】

【文中算法思路】
1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。
2、我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。
4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。

class Solution {
    String source, target;
    Map<Character, Integer> targetCharCount;
    Map<Character, Integer> windowCharCount;
    int left, right;
    int windowValidChars;
    int minWindowStart, minWindowLength;

    public String minWindow(String s, String t) {
        init(s, t);  //  第 1 步，初始化
        while (canExpand()) { // 第 4 步，重复第 2，3 步
            while (canExpand() && !windowContainsSolution()) expandWindow();  // 第 2 步，扩大窗口

            while (windowContainsSolution()) {  // 第 3 步
                updateSolution();  //  更新结果
                shrinkWindow();  //  缩小窗口
            }
        }

        return getSolution();
    }

    void init(String source, String target) {
        this.source = source;
        this.target = target;

        targetCharCount = getCharCount(target);
        windowCharCount = new HashMap<>(targetCharCount.size());

        left = 0;
        right = 0;
        windowValidChars = 0;
        minWindowStart = 0;
         minWindowLength = Integer.MAX_VALUE;
    }

    Map<Character, Integer> getCharCount(String s) {
        int n = s.length();
        Map<Character, Integer> charToCount = new HashMap<>(n);
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            charToCount.put(c, charToCount.getOrDefault(c, 0) + 1);
        }

        return charToCount;
    }

    boolean canExpand() {
        return right < source.length();
    }

    boolean windowContainsSolution() {
        return windowValidChars == targetCharCount.size();
    }

    void expandWindow() {
        char c = source.charAt(right);
        int targetCount = targetCharCount.getOrDefault(c, 0);
        if (targetCount > 0) {
            int oldCount = windowCharCount.getOrDefault(c, 0);
            int newCount = oldCount + 1;
            windowCharCount.put(c, newCount);
            if (newCount == targetCount) windowValidChars++;
        }
        right++;
    }
 
    void updateSolution() {
        int thisWindowLength = right - left;    
        if (thisWindowLength < minWindowLength) {
            minWindowStart = left;
            minWindowLength = thisWindowLength;
        }
    }

    void shrinkWindow() {
        char c = source.charAt(left);
        int targetCount = targetCharCount.getOrDefault(c, 0);
        if (targetCount != 0) {
            int oldCount = windowCharCount.get(c); 
            windowCharCount.put(c, oldCount - 1);
            if (oldCount == targetCount) windowValidChars--;
        }
        left++;
    }

    String getSolution() {
        return minWindowLength == Integer.MAX_VALUE ? "" : source.substring(minWindowStart, minWindowStart + minWindowLength);
    }
}

[leslie0007]

没看懂时：写什么玩意
看懂之后：妙啊

[smallkaka]

一套打通，感谢。写的很丝滑，不用硬套，理解窗口的作用，直接根据题目加上自己对题目的限制条件的理解。

[pengxl8518]

写的肿不错啊