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

[utterances-bot]

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

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

[lipku]

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

[Fightjiang]

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

[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]

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

[tt110617]

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

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

这样写可以过LeetCode

class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character,Integer> window = new HashMap<>();
        int left = 0, right = 0;
        int res = 0;
        while (right < s.length()) {          
            // c 是移入窗口的字符
            char c = s.charAt(right);
            // 窗口右移
            right++;
            // 更新窗口的一系列数据
            window.put(c, window.getOrDefault(c, 0) + 1);

                // 判断左侧窗口是否需要收缩
                while (window.get(c) > 1) {
                    // d 是移出窗口的字符
                    char d = s.charAt(left);
                    // 窗口右移
                    left++;
                    // 更新窗口的一系列数据
                    window.put(d, window.get(d) - 1);
                }
                // 这里更新最长子串的长度
                int len = right - left;
                res = Math.max(res, len);
        }
        return res;
    }
}

[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进行匹配

[PeachLuis]

76题，我照着改的java版本，为什么有一个测试用例通不过，这个测试用例特长

    public String minWindow(String s, String t) {
        //初始化nee和window，K-V存 字符-次数
        Map<Character,Integer> need = new HashMap<>();
        Map<Character,Integer> window = new HashMap<>();
        //初始化need
        for(int i=0;i<t.length();i++){
            char c = t.charAt(i);
            need.put(c, need.getOrDefault(c,0) + 1);
        }

        //滑动窗口的左右指针 [left,right)
        int left = 0, right = 0;
        //最小覆盖的起始索引，长度
        int start = 0, len = Integer.MAX_VALUE;
        int valid = 0;      //window中满足个数
        //char[] chars = s.toCharArray();
        while(right < s.length()){
            //扩大窗口
            //char c = chars[right];
            char c = s.charAt(right);
            right++;    //右移窗口
            //进行窗口内数据的一系列更新
            if(need.containsKey(c)){
                window.put(c, window.getOrDefault(c,0) + 1);
                if(window.get(c) == need.get(c)){
                    valid++;
                }
            }

            //判断左侧窗口是否要收缩
            while(valid == need.size()){
                // 更新最小覆盖子串
                if(right - left < len){
                    start = left;
                    len = right - left;
                }
                //左移窗口
                //char d = chars[left];
                char d = s.charAt(left);
                left++;
                //进行窗口内数据的更新
                if(need.containsKey(d)){
                    if(window.get(d) == need.get(d)){
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start,start+len);
    }

[PeachLuis]

ok，把 == 改为equals就通过了，但是这是比较整数，为什么不行

[PeachLuis]

ok，我懂了，Map存的是Integer，超过128了

[Jackwong0716]

滑动窗口那个right代表的下标是可以取到的，似乎不是左闭右开 。如果把right理解为第几个，因为数组下标是从0开始，那么right是开的。

[Jackwong0716]

这个窗口，可以理解为，左闭右闭窗口吗？？因为那个while(right < s.size()) ,它是取不到s. size(), 但是right可以取到，这样可以理解为是左闭右闭吗？？

[labuladong]

@Jackwong0716 这个所谓开闭的概念，不是看循环中是 < 还是 <=，而是看取到的这个值是否是合法的索引。while(right < s.size()) 中 right 确实可以取到 s. size()，但是这个值是一个越界的索引，所以我们让 right 这一边是开区间：

即便 right 取到了越界索引，但这个 [left, right) 左闭右开区间窗口中的元素都是合法的。

[jingb]

老哥 小灯泡那个图标鼠标悬停可以引用展示前面的内容是怎么实现的？这个功能好强大实用呀

[861130245]

不得不说,框架的力量确实牛

[JingweiZuo]

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

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

的确，东哥的框架可以直接套用 不过为了方便理解 也可以先判断窗口大小，再更新结果；Python代码如下

Python 438. Find All Anagrams in a String

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        #sliding window with two pointers
        pl, pr = 0, 0
        need = dict()
        window = dict()
        valid = 0
        res = []
        for e in p:
            if e not in need:
                need.update({e:1})
            else:
                need[e] += 1
                
        #window: [pl, pr)
        while pr < len(s):
            right = s[pr]
            pr += 1
            if right in need:
                if right not in window:
                    window.update({right:1})
                else:
                    window[right] += 1
                if window[right] == need[right]:
                    valid += 1
            #check if we need to shunk the window 
            #Key point: check the window size
            while pr - pl > len(p):
                left = s[pl]
                pl += 1
                if left in need:
                    if window[left] == need[left]:
                        valid -= 1
                    window[left] -= 1
            if valid == len(need):
                res.append(pl)
        return res

[Goolloo]

76 Java 版

public String minWindow(String s, String t) {
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        
        // tracking index
        int left = 0;
        int right = 0;
        int valid = 0;
        // min result index
        int minLeft = 0;
        int minRight = Integer.MAX_VALUE;
        while(right < s.length()) {
            char toAdd = s.charAt(right);
            right++;
            if(need.containsKey(toAdd)) {
                window.put(toAdd, window.getOrDefault(toAdd, 0) + 1);
                
                if(window.get(toAdd).equals(need.get(toAdd))) {
                    valid++;
                }
            }
            
            
            while(valid == need.size()) {
                if((right - left) < (minRight - minLeft)) {
                    minLeft = left;
                    minRight = right;
                }
                
                char toRemove = s.charAt(left);
                left++;
                
                if(need.containsKey(toRemove)) {
                    if(window.get(toRemove).equals(need.get(toRemove))) {
                        valid--;
                    }
                    window.put(toRemove, window.get(toRemove) - 1);
                }
            }
        }
        
        return minRight == Integer.MAX_VALUE ? "" : s.substring(minLeft, minRight);
    }

[Goolloo]

76 Java 通过减数法节省一个Map

public String minWindow(String s, String t) {
        Map<Character, Integer> validCharToCountMap = new HashMap<>();
        for(char c : t.toCharArray()) {
            validCharToCountMap.put(c, validCharToCountMap.getOrDefault(c, 0) + 1);
        }
        
        // moving counts
        int left = 0;
        int right = 0;
        int validCharCount = 0;
        // result counts
        int minLeft = 0; 
        int minRight = Integer.MAX_VALUE;
        while(right < s.length()) {
            char toAdd = s.charAt(right);
            right++;

            if(validCharToCountMap.containsKey(toAdd)) {
                validCharToCountMap.put(toAdd, validCharToCountMap.get(toAdd) - 1);
                if (validCharToCountMap.get(toAdd) == 0) {
                    validCharCount++;
                }
            }
            
            while(validCharToCountMap.keySet().size() == validCharCount) {                
                // update min length variables
                if((right - left) < (minRight - minLeft)) {                    
                    minRight = right;
                    minLeft = left;
                }

                // remove left most char
                char toRemove = s.charAt(left);
                left++;

                // update count
                if(validCharToCountMap.containsKey(toRemove)) {
                    validCharToCountMap.put(toRemove, validCharToCountMap.get(toRemove) + 1);
                    if(validCharToCountMap.get(toRemove) > 0) {
                        validCharCount--;
                    }
                }
            }
        }
        
        if(minRight == Integer.MAX_VALUE) {
            return "";
        }
        
        return s.substring(minLeft, minRight);
    }

[MathsGo]

最后一行有笔误 滑动窗口就讲到这里 不是 就降到这里

[MathsGo]

现在开始增加 left，缩小窗口 [left, right]：

这一行有笔误

不是左闭右开吗？ right后面应该是小括号吧

[yh284914425]

if (need.count(c)) {
         window[c]++;
         if (window[c] == need[c])
             valid++;
     }

和

if (need.count(d)) {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }

一个先 window[c]++;在判断 一个 先判断 window[d]--; 这里怎么理解比较好呀