0
  • 聊天消息
  • 系统消息
  • 评论与回复
登录后你可以
  • 下载海量资料
  • 学习在线课程
  • 观看威廉希尔官方网站 视频
  • 写文章/发帖/加入社区
会员中心
创作中心

完善资料让更多小伙伴认识你,还能领取20积分哦,立即完善>

3天内不再提示

滑动窗口算法解决子串问题教程

jf_78858299 来源:labuladong 作者:labuladong 2023-04-19 11:06 次阅读

现在写滑动窗口算法的时机应该是合适的,因为读者已经通过 [双指针技巧汇总]理解了双指针的套路,通过 [单调队列解决滑动窗口问题]对滑动窗口这个东西有了个印象,而且通过 [一个方法团灭股票问题] 看到了成体系方法举一反三的威力。

本文详解「滑动窗口」这种高级双指针技巧的算法框架,带你秒杀几道高难度的子字符串匹配问题。

LeetCode 上至少有 9 道题目可以用此方法高效解决。但是有几道是 VIP 题目,有几道题目虽不难但太复杂,所以本文只选择点赞最高,较为经典的,最能够讲明白的三道题来讲解。第一题为了让读者掌握算法模板,篇幅相对长,后两题就基本秒杀了。文章最后抽象出一个简单的算法框架。

本文代码为 C++ 实现,不会用到什么编程方面的奇技淫巧,但是还是简单介绍一下一些用到的数据结构,以免有的读者因为语言的细节问题阻碍对算法思想的理解:

unordered_map 就是哈希表(字典),它的一个方法 count(key) 相当于 containsKey(key) 可以判断键 key 是否存在。

可以使用方括号访问键对应的值 map[key]。需要注意的是,如果该 key 不存在,C++ 会自动创建这个 key,并把 map[key] 赋值为 0。

所以代码中多次出现的 map[key]++ 相当于 Java 的 map.put(key, map.getOrDefault(key, 0)+1)。

PS:本文大的主要代码都是图片形式,可以点开放大,更重要的是可以左右滑动方便对比代码。

一、最小覆盖子串

图片

题目不难理解,要求在串 S(source) 中找到包含串 T(target) 中全部字母的一个子串,顺序无所谓,但这个子串得是所有可能子串中最短的。

此题难度 Hard,但是因为很有代表性,所以放到第一道。

如果我们使用暴力解法,代码大概是这样的:

for (int i = 0; i < s.size(); i++)
    for (int j = i + 1; j < s.size(); j++)
        if s[i:j] 包含 t 的所有字母:
            更新答案

思路很直接吧,但是显然,这个算法的复杂度肯定大于 O(N^2) 了,不好。

滑动窗口算法的思路是这样:

1 、我们在字符串 S 中使用双指针中的左右指针技巧,初始化 left = right = 0,把索引闭区间 [left, right] 称为一个「窗口」。

2 、我们先不断地增加 right 指针扩大窗口 [left, right],直到窗口中的字符串符合要求(包含了 T 中的所有字符)。

3 、此时,我们停止增加 right,转而不断增加 left 指针缩小窗口 [left, right],直到窗口中的字符串不再符合要求(不包含 T 中的所有字符了)。同时,每次增加 left,我们都要更新一轮结果。

4 、重复第 2 和第 3 步,直到 right 到达字符串 S 的尽头。

这个思路其实也不难, 第 2 步相当于在寻找一个「可行解」,然后第 3 步在优化这个「可行解」,最终找到最优解。 左右指针轮流前进,窗口大小增增减减,窗口不断向右滑动。

下面画图理解一下,needs 和 window 相当于计数器,分别记录 T 中字符出现次数和窗口中的相应字符的出现次数。

初始状态:

图片

增加 right,直到窗口 [left, right] 包含了 T 中所有字符:

图片

现在开始增加 left,缩小窗口 [left, right](此时窗口里的字符串是最优解):

图片

直到窗口中的字符串不再符合要求,left 不再继续移动:

图片

之后重复上述过程,再移动 right 试图使窗口中的字符再次符合要求,之后移动 left 缩小窗口… 直到 right 指针到达字符串 S 的末端,算法结束。

在算法执行过程中,就可以找到长度最短符合条件的子串(窗口)。

如果你能够理解上述过程,恭喜,你已经完全掌握了滑动窗口算法思想。至于如何具体到问题,如何得出此题的答案,都是编程问题,很容易解决。

上述过程可以简单地写出如下伪码框架:

string s, t;
// 在 s 中寻找 t 的「最小覆盖子串」
int left = 0, right = 0;
string res = s;
// 先移动 right 寻找可行解
while(right < s.size()) {
    window.add(s[right]);
    right++;
    // 找到可行解后,开始移动 left 缩小窗口
    while (window 符合要求) {
        // 如果这个窗口的子串更短,则更新结果
        res = minLen(res, window);
        window.remove(s[left]);
        left++;
    }
}
return res;

如果上述代码你也能够理解,那么你离解题更近了一步。现在就剩下一个比较棘手的问题:

如何判断 window 即子串 s[left...right] 是否符合要求,即是否包含 t 的所有字符呢?

可以用两个哈希表当作计数器解决。用一个哈希表 needs 记录字符串 t 中包含的字符及出现次数,用另一个哈希表 window 记录当前「窗口」中包含的字符及出现的次数。如果 window 包含所有 needs 中的键,且这些键对应的值都大于等于 needs 中的值,那么就可以知道当前「窗口」符合要求了,可以开始移动 left 指针了。

现在将上面的框架继续细化:

图片

上述代码已经具备完整的逻辑了,只有一处伪码,即更新最短子串结果 res 的地方,不过这个问题太好解决了,直接看完整解法吧!

图片

如果直接甩给你这么一大段代码,我想你的心态是爆炸的。但是通过之前的步步跟进,你应该能够理解这个算法的内在逻辑,能清晰看出该算法的结构了。

这个算法的时间复杂度是 O(M + N),M 和 N 分别是字符串 S 和 T 的长度。因为我们先用 for 循环遍历了字符串 T 来初始化 needs,时间 O(N),之后的两个 while 循环最多执行 2M 次,时间 O(M)。

读者也许认为嵌套的 while 循环复杂度应该是平方级,但是你这样想,while 执行的次数就是双指针 left 和 right 走的总路程,最多是 2M 嘛。

二、找到字符串中所有字母异位词

图片

这道题的难度是 Easy,但是评论区点赞最多的一条是这样:

How can this problem be marked as easy?

实际上,这个 Easy 是属于了解双指针技巧的人的,只要把上一道题的代码改中更新结果的代码稍加修改就成了这道题的解:

图片

因为这道题和上一道的场景类似,也需要 window 中包含串 t 的所有字符,但上一道题要找长度最短的子串,这道题要找长度相同的子串,也就是「字母异位词」嘛。

三、无重复字符的最长子串

图片

此题难度 Medium,遇到子串问题,首先想到的就是滑动窗口技巧。

类似之前的思路,使用 window 作为计数器记录窗口中的字符出现次数,然后先向右移动 right,当 window 中出现重复字符时,开始移动 left 缩小窗口,如此往复:

图片

需要注意的是,因为我们要求的是最长子串,所以需要在每次移动 right 增大窗口时更新 res,而不是像之前的题目在移动 left 缩小窗口时更新。

四、模板总结

通过上面三道题,我们可以总结出滑动窗口算法的抽象思想:

int left = 0, right = 0;

while (right < s.size()) {
    window.add(s[right]);
    right++;

    while (valid) {
        window.remove(s[left]);
        left++;
    }
}

其中 window 的数据类型可以视具体情况而定,比如上述题目都使用哈希表充当计数器,当然你也可以用一个数组实现同样效果,因为我们只处理英文字母。

另外,滑动窗口技巧也可以运用在数组中,比如给一个数组,求其中 sum 最大的子数组,或者求平均数最大的子数组,都可以用滑动窗口技巧解决。

稍微麻烦的地方就是这个 valid 条件,为了实现这个条件的实时更新,我们可能会写很多代码。比如前两道题,看起来解法篇幅那么长,实际上思想还是很简单,只是大多数代码都在处理这个问题而已。

声明:本文内容及配图由入驻作者撰写或者入驻合作网站授权转载。文章观点仅代表作者本人,不代表电子发烧友网立场。文章及其配图仅供工程师学习之用,如有内容侵权或者其他违规问题,请联系本站处理。 举报投诉
  • 算法
    +关注

    关注

    23

    文章

    4610

    浏览量

    92859
  • 滑动窗口法
    +关注

    关注

    0

    文章

    5

    浏览量

    2151
  • leetcode
    +关注

    关注

    0

    文章

    20

    浏览量

    2318
收藏 人收藏

    评论

    相关推荐

    TCP协议拥塞控制的滑动窗口协议解析

    TCP协议作为一个可靠的面向流的传输协议,其可靠性和流量控制由滑动窗口协议保证,而拥塞控制则由控制窗口结合一系列的控制算法实现。
    的头像 发表于 10-08 17:04 2930次阅读
    TCP协议拥塞控制的<b class='flag-5'>滑动</b><b class='flag-5'>窗口</b>协议解析

    窗口问题

    程序包含一个主界面和一个窗口窗口用于实时更新状态信息,更新频率较为频繁。目前窗口作为一个
    发表于 02-08 14:58

    请问SetParent绑架的窗口如何释放

    用SetParent函数将窗口绑架到母窗口没有问题,也可以对被绑架的窗口进行设置调节,但是在释放的时候,
    发表于 09-14 10:38

    滑动窗口

    假设D=double(1,515), A=cell(1,103),窗口长度为25,滑动距离为5,从D(1)开始滑动窗口直到D的末尾,右端缺失部分补零,共得到103个
    发表于 11-22 11:22

    Delphi教程_从外部DLL中调用窗口

    Delphi教程从外部DLL中调用窗口,很好的Delphi资料,快来下载学习吧。
    发表于 03-16 14:49 5次下载

    基于滑动窗口法的智能开关动作时间动态预测_郑贵林

    基于滑动窗口法的智能开关动作时间动态预测_郑贵林
    发表于 01-18 20:21 0次下载

    基于滑动窗口的多核程序数据竞争硬件检测算法

    数据竞争是引起多核程序发生并发错误的主要原因。针对现有基于硬件的happens-before数据竞争检测方法硬件开销大的问题,提出了一种轻量级的内存竞争硬件检测算法,该算法利用滑动窗口
    发表于 02-07 13:33 0次下载
    基于<b class='flag-5'>滑动</b><b class='flag-5'>窗口</b>的多核程序数据竞争硬件检测<b class='flag-5'>算法</b>

    对于绝缘,它的电压分布规律是什么

    在使用绝缘测试仪系列产品对日常运行中的绝缘实际巡检、维护中,我们可以根据绝缘的电压分布规律及安装使用环境来决定检测绝缘
    的头像 发表于 03-30 21:48 1.4w次阅读

    快慢指针、左右指针的常见算法

    技巧秒杀 5 道算法题。 其实,鼎鼎有名的「滑动窗口算法」就是一种双指针技巧,我们之前的爆文我写了套框架,把滑动窗口算法变成了默写题就有这么
    的头像 发表于 11-26 14:09 2480次阅读

    基于MBNS滑动窗口的多标量乘快速算法

      针对椭圆曲线密码体制中标量乘与多标量乘运算耗时过长的问题,设计以2、3、7为基元的多基整数表示方法,并结合多基数系统(MBNS)及滑动窗口算法,提出基于MBNS滑动窗口( Slid
    发表于 03-11 11:17 18次下载
    基于MBNS<b class='flag-5'>滑动</b><b class='flag-5'>窗口</b>的多标量乘快速<b class='flag-5'>算法</b>

    基于滑动窗口的宽度优先搜索算法

    数据。针对此类数据,设计基于滑动窗口、 Apriori性质和贪心选择策略的宽度优先搜索算法,对移动对象伴随模式挖掘问题进行求解。同时结合基于哈希的迭代剪枝算法和基于摘要信息的剪枝
    发表于 04-27 14:14 4次下载
    基于<b class='flag-5'>滑动</b><b class='flag-5'>窗口</b>的宽度优先搜索<b class='flag-5'>算法</b>

    labview主窗口窗口之间的切换

    labview主窗口窗口之间的切换
    发表于 11-01 15:55 73次下载

    语音芯片在口算训练仪的应用

    ,完全替代了传统口算练习册,如同玩游戏一般轻松练习口算,也节省了家长检查对错的时间。 口算训练仪拥有多个按键组成,每个按键对应不同的数字与功能,内有加减乘数等算法,通过语音播报的
    发表于 06-24 15:01 649次阅读

    关于go语言实现的几种限流算法介绍

    滑动时间窗口算法,是从对普通时间窗口计数的优化。使用普通时间窗口时,我们会为每个user_id/ip维护一个KV: uidOrIp: timestamp_requestCount。
    发表于 04-01 10:37 627次阅读

    滑动窗口算法技巧

    说起滑动窗口算法,很多读者都会头疼。这个算法技巧的思路非常简单,就是维护一个窗口,不断滑动,然后更新答案么。LeetCode 上有起码 10
    的头像 发表于 04-19 10:55 906次阅读
    <b class='flag-5'>滑动</b><b class='flag-5'>窗口算法</b>技巧