滑动窗口（Sliding Window）技巧总结

什么是滑动窗口（Sliding Window）

The Sliding Problem contains a sliding window which is a sub – list that runs over a Large Array which is an underlying collection of elements.

滑动窗口算法可以用以解决数组/字符串的子元素问题，它可以将嵌套的循环问题，转换为单循环问题，降低时间复杂度。

比如找最长的全为1的子数组长度。滑动窗口一般从第一个元素开始，一直往右边一个一个元素挪动。当然了，根据题目要求，我们可能有固定窗口大小的情况，也有窗口的大小变化的情况。

该图中，我们窗口一格一格往右移动

如何判断使用滑动窗口算法

如果题目中求的结果有以下情况时可使用滑动窗口算法：

  • 最小值 Minimum value
  • 最大值 Maximum value
  • 最长值 Longest value
  • 最短值 Shortest value
  • K值 K-sized value

算法模板与思路

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    
    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        printf("window: [%d, %d)\n", left, right);
        /********************/
        
        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

滑动窗口算法的思路：

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

needs 和 window 相当于计数器，分别记录 T 中字符出现次数和「窗口」中的相应字符的出现次数。

开始套模板之前，要思考以下四个问题：

  1. 当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？
  2. 什么条件下，窗口应该暂停扩大，开始移动left 缩小窗口？
  3. 当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？
  4. 我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？

滑动窗口问题实例

最小覆盖子串

LeetCode题目：76.最小覆盖子串

76.最小覆盖子串

1、阅读且分析题目

题目中包含关键字：时间复杂度O(n)、字符串、最小子串。可使用滑动窗口算法解决。

2. 思考滑动窗口算法四个问题

1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？

更新 window 中加入字符的个数，判断 need 与 window 中的字符个数是否相等，相等则 valid++ 。

2、什么条件下，窗口应该暂停扩大，开始移动left 缩小窗口？

当 window 包含 need 中的字符及个数时，即 valid == len(need) 。

3、当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？

更新 window 中移出字符的个数，且判断 need 与 window 中的移出字符个数是否相等，相等则 valid-- 。

4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？

在缩小窗口时，因为求的是最小子串。

3. 代码实现

func minWindow(s string, t string) string {
    need, window := make(map[byte]int), make(map[byte]int)
    for i := 0; i < len(t); i++ { // 初始化 need 
        if _, ok := need[t[i]]; ok {
            need[t[i]]++
        } else {
            need[t[i]] = 1
        }
    }

    left, right, valid := 0, 0, 0
    start, slen := 0, len(s)+1 // 设置长度为 len(s) + 1 表示此时没有符合条件的子串
    for right < len(s) { // 滑动窗口向右扩大
        c := s[right]
        right++

        if _, ok := need[c]; ok { // 向右扩大时，更新数据
            if _, ok := window[c]; ok {
                window[c]++
            } else {
                window[c] = 1
            }

            if window[c] == need[c] {
                valid++
            }
        }

        for valid == len(need) { // 当窗口包括 need 中所有字符及个数时，缩小窗口

            if right-left < slen {  // 缩小前，判断是否最小子串
                start = left
                slen = right - left
            }

            d := s[left]
            left++

            if v, ok := need[d]; ok { // 向左缩小时，更新数据
                if window[d] == v {
                    valid--
                }
                window[d]--
            }
        }
    }

    if slen == len(s)+1 { // 长度 len(s) + 1 表示此时没有符合条件的子串
        return ""
    } else {
        return s[start : start+slen]
    }
}

4. 复杂度分析

  • 时间复杂度：O(n)，n 表示字符串 s 的长度。遍历一次字符串。
  • 空间复杂度：O(m)，m 表示字符串 t 的长度。使用了两个哈希表，保存字符串 t 中的字符个数。

字符串排列

LeetCode题目：567.字符串的排列

567.字符串的排列

1、阅读且分析题目

题目中包含关键字：字符串、子串，且求 s2 中是否包含 s1 的排列，即求是否包含长度 k 的子串。可使用滑动窗口算法解决。

2. 思考滑动窗口算法四个问题

1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？

更新 window 中加入字符的个数，判断 need 与 window 中的字符个数是否相等，相等则 valid++ 。

2、什么条件下，窗口应该暂停扩大，开始移动left 缩小窗口？

当 window 包含 need 中的字符及个数时，即 valid == len(need) 。

3、当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？

更新 window 中移出字符的个数，且判断 need 与 window 中的移出字符个数是否相等，相等则 valid-- 。

4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？

无论在扩大时或缩小窗口时都可以，因为求的是固定长度的子串。选择在缩小窗口时更新。

3. 代码实现

func checkInclusion(s1 string, s2 string) bool {
    if s1 == s2 {
        return true
    }

    need, window := make(map[byte]int), make(map[byte]int)

    for i := 0; i < len(s1); i++ {
        if _, ok := need[s1[i]]; ok {
            need[s1[i]]++
        } else {
            need[s1[i]] = 1
        }
    }

    left, right := 0, 0
    valid := 0

    for right < len(s2) {
        c := s2[right]
        right++

        if _, ok := need[c]; ok {
            if _, ok := window[c]; ok {
                window[c]++
            } else {
                window[c] = 1
            }
            if window[c] == need[c] {
                valid++
            }
        }

        for valid == len(need) {

            if right-left == len(s1) {
                return true
            }

            d := s2[left]
            left++

            if _, ok := need[d]; ok {
                if _, ok := window[d]; ok {
                    if window[d] == need[d] {
                        valid--
                    }
                    window[d]--
                }
            }
        }
    }

    return false
}

4. 复杂度分析

  • 时间复杂度：O(n)，n 表示字符串 s2 的长度。遍历一次字符串。
  • 空间复杂度：O(m)，m 表示字符串 s1 的长度。使用了两个哈希表，保存字符串 s1 中的字符个数。

找所有字母异位词

LeetCode题目：438.找到字符串中所有字母异位词

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

1、阅读且分析题目

题目中包含关键字：字符串，且求 s 中的所有 p 的字母异位词的子串。可使用滑动窗口算法解决。

2. 思考滑动窗口算法四个问题

1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？

更新 window 中加入字符的个数，判断 need 与 window 中的字符个数是否相等，相等则 valid++ 。

2、什么条件下，窗口应该暂停扩大，开始移动left 缩小窗口？

当 window 包含 need 中的字符及个数时，即 valid == len(need) 。

3、当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？

更新 window 中移出字符的个数，且判断 need 与 window 中的移出字符个数是否相等，相等则 valid-- 。

4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？

无论在扩大时或缩小窗口时都可以，因为求的是固定长度的子串。选择在缩小窗口时更新。

3. 代码实现

func findAnagrams(s string, p string) []int {
    need, window := make(map[byte]int), make(map[byte]int)
    for i := 0; i < len(p); i++ { // 初始化
        if _, ok := need[p[i]]; ok {
            need[p[i]]++
        } else {
            need[p[i]] = 1
        }
    }

    left, right := 0, 0
    valid := 0

    ans := make([]int, 0)

    for right < len(s) {
        c := s[right]
        right++

        if _, ok := need[c]; ok {
            if _, ok := window[c]; ok {
                window[c]++
            } else {
                window[c] = 1
            }
            if need[c] == window[c] {
                valid++
            }
        }

        for valid == len(need) {
            if right-left == len(p) {
                ans = append(ans, left)
            }

            d := s[left]
            left++

            if _, ok := need[d]; ok {
                if _, ok := window[d]; ok {
                    if need[d] == window[d] {
                        valid--
                    }
                    window[d]--
                }
            }
        }
    }

    return ans
}

4. 复杂度分析

  • 时间复杂度：O(n)，n 表示字符串 s 的长度。遍历一次字符串。
  • 空间复杂度：O(m)，m 表示字符串 p 的长度。使用了两个哈希表，保存字符串 p 中的字符个数。

最长无重复子串

LeetCode题目：3. 无重复字符的最长子串

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

1、阅读且分析题目

题目中包含关键字：时间复杂度O(n)、字符串、最小子串。可使用滑动窗口算法解决。

2. 思考滑动窗口算法四个问题

1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？

更新 window 中加入字符的个数，及当 window 中的某个字符个数 == 2时，更新 valid == false 。

2、什么条件下，窗口应该暂停扩大，开始移动left 缩小窗口？

当 window 中的字符及个数 == 2时，即 valid == false 。

3、当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？

更新 window 中移出字符的个数，且判断 window 中移出字符个数是否 == 2 ，相等则 valid == true 。

4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？

在扩大窗口时，因为求的是最大子串。

3. 代码实现

func lengthOfLongestSubstring(s string) int {
    if s == "" { // 当字符串为空时，返回0
        return 0
    }

    window := make(map[byte]int)

    left, right, max := 0, 0, 0
    valid := true

    for right < len(s) {
        c := s[right]
        right++

        if _, ok := window[c]; !ok { // 初始化
            window[c] = 0
        }
        window[c]++         // 累加
        if window[c] == 2 { // 当出现重复字符时
            valid = false
        } else { // 否则累加不重复子串长度，并且判断是否当前最长
            if max < right-left {
                max = right - left
            }
        }

        for valid == false {
            d := s[left]
            left++

            if window[d] == 2 {
                valid = true
            }
            window[d]--
        }
    }
    return max
}

4. 复杂度分析

  • 时间复杂度：O(n)，n 表示字符串 s 的长度。遍历一次字符串。
  • 空间复杂度：O(n)，n 表示字符串 s 的长度。使用了哈希表，保存不重复的字符个数。

总结

  • 滑动窗口算法可以用以解决数组/字符串的子元素问题，它可以将嵌套的循环问题，转换为单循环问题，降低时间复杂度。
  • 问题中包含字符串子元素、最大值、最小值、最长、最短、K值等关键字时，可使用滑动窗口算法。
  • 模板中的向左和向右时的处理是对称的。
  • 套模板前思考四个问题：
    1. 当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？
    2. 什么条件下，窗口应该暂停扩大，开始移动left 缩小窗口？
    3. 当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？
    4. 我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？

参考资料

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 203,671评论 6赞 477
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,442评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,524评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,623评论 1赞 275
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,642评论 5赞 365
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,584评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,953评论 3赞 395
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,621评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,865评论 1赞 297
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,608评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,698评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,378评论 4赞 318
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,958评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,940评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,173评论 1赞 259
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 44,419评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,425评论 2赞 342