滑动窗口算法：巧妙玩转数据的窗外世界

✨✨✨学习的道路很枯燥，希望我们能并肩走下来!

文章目录

目录

文章目录

前言

一 滑动窗口是什么？

二 相关题目解析

1. 长度最小的子数组

🥳题目解析 

🥳算法原理 

✏️思路1  暴力枚举出所有子数组之和

 ✏️思路2 滑动窗口

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

🥳题目解析 

🥳算法原理 

✏️思路1  暴力枚举 + 哈希表

✏️思路2 滑动窗口优化+哈希表

3. 最大连续1的个数 III

🥳题目解析 

 🥳算法原理 

✏️思路1  暴力枚举 + 计数器       

✏️思路2 滑动窗口优化+计数器

4.将x减到0的最小操作数

🥳题目解析 

  🥳算法原理 

✏️思路 滑动窗口（正难则反

5. 水果成篮

🥳题目解析 

🥳算法原理 

✏️思路 滑动窗口+哈希表

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

🥳题目解析 

🥳算法原理

✏️思路 滑动窗口+哈希表

7. 串联所有单词的字串 

🥳题目解析  

🥳算法原理  

✏️思路 滑动窗口+哈希表​编辑 

8. 最小覆盖字串  

🥳题目解析  

🥳算法原理

✏️思路 滑动窗口+哈希表

总

前言

本篇详细介绍了滑动窗口的使用，让使用者了解滑动窗口，而不是仅仅停留在表面，更好的模拟，为了更好的使用. 文章可能出现错误，如有请在评论区指正，让我们一起交流，共同进步！

一 滑动窗口是什么？

其实就是我们前文提到的同向指针（前后指针

 一般情况下，我们利用同向双指针来维护一个区间，在移动区间的过程中像一个窗口滑来滑去，因此称为滑动窗口

简而言之，滑动窗口算法在一个特定大小的字符串或数组上进行操作，而不在整个字符串和数组上操作，这样就降低了问题的复杂度，从而也达到降低了循环的嵌套深度。其实这里就可以看出来滑动窗口主要应用在数组和字符串上。 

什么时候用滑动窗口？

1. 同向双指针

2. 指针不回退

二 相关题目解析

1. 长度最小的子数组

🥳题目解析 

209. 长度最小的子数组 - 力扣（LeetCode）

这道题要求我们返回符合条件的子数组的最小长度，没有则返回0 

🥳算法原理 

✏️思路1  暴力枚举出所有子数组之和

暴力枚举出所有子数组之和，时间复杂度为O（N2）

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int ans = INT_MAX;
        for (int i = 0; i < n; i++) {
            int sum = 0; //利用sum边走边++，使得不用再遍历一遍
            for (int j = i; j < n; j++) {
                sum += nums[j];
                if (sum >= s) {
                    ans = min(ans, j - i + 1);
                    break;
                }
            }
        }
        return ans == INT_MAX ? 0 : ans;
    }
};
 ✏️思路2 滑动窗口

我们在暴力解法的过程中发现，有一些情况是没有必要枚举出来的（一定不符合要求 

 

当我们移动到如图上所示时，子数组的值已经大于target，

如果我们继续扩大窗口， 子数组的值一定仍大于target，但子数组的长度不断扩大，与我们的最小子数组长度不符，因此无需枚举后面的情况。

 

代码解析

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sum = 0, len = INT_MAX; //给最大，方便更新结果
        for(int left = 0,right =0;right<nums.size();right++)
        {
            sum+=nums[right]; //进窗口
            while(sum>=target)//判断
            {
                len = min(len,right-left+1); //更新结果
                sum-=nums[left++]; //出窗口
            }
        }

        return len == INT_MAX ? 0 : len;
    }
};

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

🥳题目解析 

3. 无重复字符的最长子串 - 力扣（LeetCode）

🥳算法原理 

✏️思路1  暴力枚举 + 哈希表

         固定一个数，从左到右遍历，将每个数放进哈希表，遇到重复的数停止，更新数据，固定数位置右移重复上述操作

✏️思路2 滑动窗口优化+哈希表

 

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hax[128]={0}; //利用数组来模拟哈希表
        int left = 0, right = 0;
        int ret = 0;
        while(right<s.size())
        {
            hax[s[right]]++;  //进窗口
            while(hax[s[right]]>1)  //判断重复
                hax[s[left++]]--; //出窗口
            ret = max(ret,right-left+1); //更新结果
            right++; //让下一个元素进入窗口
        }
        return ret;
    }
};

3. 最大连续1的个数 III

🥳题目解析 

1004. 最大连续1的个数 III - 力扣（LeetCode）

 🥳算法原理 

✏️思路1  暴力枚举 + 计数器       
for(int i = 0 ;i<nums.size();i++)
{
    for(int j = i;j<nums.size();j++)
    {
        //...zero>k
    }    
}
✏️思路2 滑动窗口优化+计数器

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int ret = 0;
        for(int left = 0,right = 0,zero = 0;right<nums.size();right++)
        {
            if(nums[right] == 0) //进窗口
                zero++;
            while(zero>k) //判断
            {
                if(nums[left++]==0) //出窗口
                    zero--;
            }
            ret = max(ret,right-left+1); //更新结果
        }
        return ret;
    }
};

4.将x减到0的最小操作数

🥳题目解析 

  🥳算法原理 

✏️思路 滑动窗口（正难则反

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = 0;
        for(auto&e : nums)
            sum+=e;
        int tmp = 0, len = -1;
        int target = sum - x;
        if(target<0)
            return -1;
        for(int left = 0 ,right = 0 ;right<nums.size();right++)
        {
            tmp+=nums[right];
            while(tmp>target)
            {
                tmp-=nums[left++];
            }
            if(tmp == target)
                len = max(len,right - left + 1);
        }
        if(len == -1)
            return len;
        else return nums.size()-len;
    }
};

5. 水果成篮

904. 水果成篮 - 力扣（LeetCode）

🥳题目解析 

🥳算法原理 

✏️思路 滑动窗口+哈希表

因为题目中提到

  • 1 <= fruits.length <= 105

 因此我们可以用数组来代替哈希表

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int hash[100001] = {0};//统计窗口内出现了多少种水果
        int ret = 0;
        for(int left = 0,right = 0, kinds = 0;right<fruits.size();right++)
        {
            if(hash[fruits[right]] == 0)
                kinds++;
            hash[fruits[right]]++; //进窗口
            while(kinds >2) //判断
            {
                //出窗口
                hash[fruits[left]]--;
                if(hash[fruits[left]] == 0)
                    kinds--;
                left++;
            }
            //更新结果
            ret = max(ret,right - left +1);
        }
        return ret;
    }
};

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

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

🥳题目解析 

🥳算法原理

✏️思路 滑动窗口+哈希表

 

class Solution {
public:
    bool check(int s1[],int s2[])
    {
        for(int i = 0;i<26;i++)
        {
            if(s1[i]!=s2[i])
                return false;
        }
        return true;
    }

    vector<int> findAnagrams(string s, string p) {
        int hash1[26] = {0};
        int hash2[26] = {0};
        vector<int> result;
        for(int i = 0;i<p.size();i++)
        {
            hash1[p[i]-'a']++;
        }
        for(int left = 0,right = 0;right<s.size();right++)
        {
            hash2[s[right]-'a']++;
            if(right-left+1>p.size())
            {
                hash2[s[left]-'a']--;
                left++;
            }
            if(check(hash1,hash2))
                result.push_back(left);
        }
        return result;

    }
};

 这里我们发现我们每次都要频繁的进入check函数进行检查，时间复杂度为26*n

我们可以对检查这一步骤进行优化 

 

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int hash1[26] = {0}; //统计字符串p中每个字符出现个数
        for(auto&e : p) hash1[e-'a']++;

        int hash2[26] = {0};//统计窗口中每个字符出现个数
        vector<int> ret;
        for(int left = 0,right = 0,count = 0;right<s.size();right++) //count窗口中有效字符个数
        {
            char in = s[right];
            if(++hash2[in-'a']<=hash1[in-'a']) count++; //进窗口+维护count

            if(right - left + 1 >p.size()) //判断
            {
                char out = s[left++];
                if(hash2[out-'a']--<=hash1[out-'a']) count--; //出窗口+维护count
            }
            //更新结果
            if(count == p.size()) ret.push_back(left);
        }
        return ret;

    }
};

7. 串联所有单词的字串 

30. 串联所有单词的子串 - 力扣（LeetCode） 

🥳题目解析  

此题是「438. 找到字符串中所有字母异位词」的进阶版。不同的是第 438 题的元素是字母，而此题的元素是单词。可以用类似的方法的滑动窗口来解这题。 

🥳算法原理  

✏️思路 滑动窗口+哈希表 

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string,int> hash1; //保存words里面所有单词的频率
        for(auto& e : words) hash1[e]++;

        int len = words[0].size(), n = words.size();
        for(int i = 0;i < len; i++) //执行len次
        {
            unordered_map<string,int> hash2; //保护窗口内单词的频率
            for(int left = i,right = i, count = 0;right+len<=s.size();right+=len)
            {
                //进窗口+维护count
                string in = s.substr(right,len);
                if(++hash2[in]<=hash1[in]) count++;
                //判断
                if(right-left+1>len*n)
                {
                    //出窗口+维护count
                    string out = s.substr(left,len);
                    if(hash2[out]--<=hash1[out]) count--;
                    left+=len;
                }
                //更新结果
                if(count == n) ret.push_back(left);
            }  
        }
        return ret;
    }
};

小细节优化： 

if(++hash2[in]<=hash1[in]) count++;

执行这段代码时，hash1哈希表未必有对应的单词in，这时候编译器会向hash1创建一个in，使得时间复杂度增加

优化后的代码

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string,int> hash1; //保存words里面所有单词的频率
        for(auto& e : words) hash1[e]++;

        int len = words[0].size(), n = words.size();
        for(int i = 0;i < len; i++) //执行len次
        {
            unordered_map<string,int> hash2; //保护窗口内单词的频率
            for(int left = i,right = i, count = 0;right+len<=s.size();right+=len)
            {
                //进窗口+维护count
                string in = s.substr(right,len);
                if(hash1.count(in)&&++hash2[in]<=hash1[in]) count++;
                //判断
                if(right-left+1>len*n)
                {
                    //出窗口+维护count
                    string out = s.substr(left,len);
                    if(hash1.count(out)&&hash2[out]--<=hash1[out]) count--;
                    left+=len;
                }
                //更新结果
                if(count == n) ret.push_back(left);
            }  
        }
        return ret;
    }
};

8. 最小覆盖字串  

76. 最小覆盖子串 - 力扣（LeetCode）

🥳题目解析  

🥳算法原理

✏️思路 滑动窗口+哈希表

class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = {0};
        int kinds = 0;
        for(auto& ch : t)
        {
            if(hash1[ch]==0) kinds++;
            hash1[ch]++;
        }

        int hash2[128] = {0};
        int minlen = INT_MAX, begin = -1;
        for(int left = 0,right = 0,count = 0;right<s.size();right++)
        {
            char in = s[right];
            if(++hash2[in] == hash1[in]) count++;

            while(count == kinds)
            {
                if(right-left+1<minlen)
                {
                    minlen = right-left+1;
                    begin = left;
                }
                char out = s[left++];
                if(hash2[out]-- == hash1[out]) count--;
            }
        }
        if(begin == -1) return "";
        else return s.substr(begin,minlen);
    }
};

总结

✨✨✨各位读友，本篇分享到内容是否更好的让你理解滑动窗口算法，如果对你有帮助给个👍赞鼓励一下吧！！
🎉🎉🎉世上没有绝望的处境，只有对处境绝望的人。
感谢每一位一起走到这的伙伴，我们可以一起交流进步！！！一起加油吧！！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/695964.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

LabVIEW调用DLL时需注意的问题

LabVIEW调用DLL时需注意的问题

在LabVIEW中调用DLL&#xff08;动态链接库&#xff09;是实现与外部代码集成的一种强大方式&#xff0c;但也存在一些常见的陷阱和复杂性。本文将从参数传递、数据类型匹配、内存管理、线程安全、调试和错误处理等多个角度详细介绍LabVIEW调用DLL时需要注意的问题&#xff0c;…
阅读更多...
有趣的数学 为什么绝对值和模都用两个竖线表示？

有趣的数学 为什么绝对值和模都用两个竖线表示？

绝对值和模都可以使用两个竖线表示&#xff0c;是因为它们在数学概念上有相似的性质&#xff0c;不过是应用场景不同。 绝对值&#xff08;Absolute Value&#xff09;&#xff1a; 绝对值是一个实数的非负值。它表示一个数在数轴上距离原点的距离。例如&#xff0c; 和 。 模&…
阅读更多...
Hadoop3：MapReduce源码解读之Map阶段的TextInputFormat切片机制（3）

Hadoop3：MapReduce源码解读之Map阶段的TextInputFormat切片机制（3）

Job那块的断点代码截图省略&#xff0c;直接进入切片逻辑 参考&#xff1a;Hadoop3&#xff1a;MapReduce源码解读之Map阶段的Job任务提交流程&#xff08;1&#xff09; 5、TextInputFormat源码解析 类的继承关系 它的内容比较少 重写了两个父类的方法 这里关心一下泛型参数…
阅读更多...
基于Java+SpringBoot制作一个软考助手答题小程序

基于Java+SpringBoot制作一个软考助手答题小程序

基于Java+SpringBoot制作一个软考小助手考试答题小程序。其中系统前端功能包括注册登录、公告通知、考试答题、视频课程、考试记录、题库、题目评论、错题统计、我的收藏和用户信息管理模块；系统后台功能包括用户管理、题库管理、答题管理、学习视频管理以及系统管理模块。 摘…
阅读更多...
WINUI——Behavior（行为）小结

WINUI——Behavior（行为）小结

前言 在使用MVVM进行WINUI或WPF开发时&#xff0c;Command在某些时候并不能满足逻辑与UI分离的要求。这时肯定就需要其它技术的支持&#xff0c;Behavior就是一种。在WPF中是有Behavior直接支持的&#xff0c;转到WINUI后&#xff0c;相对有一些麻烦&#xff0c;于是在此记录之…
阅读更多...
RainBond 制作应用并上架【以ElasticSearch为例】

RainBond 制作应用并上架【以ElasticSearch为例】

文章目录 安装 ElasticSearch 集群第 1 步：添加组件第 2 步：查看组件第 3 步：访问组件制作 ElasticSearch 组件准备工作ElasticSearch 集群原理尝试 Helm 安装 ES 集群RainBond 制作 ES 思路源代码Dockerfiledocker-entrypoint.shelasticsearch.yml制作组件第 1 步：添加组件…
阅读更多...
搭建RocketMQ主从异步集群

搭建RocketMQ主从异步集群

搭建RocketMQ主从异步集群 1、RocketMQ集群模式 为了追求更好的性能&#xff0c;RocketMQ的最佳实践方式都是在集群模式下完成的。RocketMQ官方提供了三种集群搭建方式&#xff1a; 2主2从异步通信方式&#xff1a;使用异步方式进行主从之间的数据复制。吞吐量大&#xff0c;…
阅读更多...
通过 AI Edge Torch 生成式 API 在设备上使用自定义大语言模型

通过 AI Edge Torch 生成式 API 在设备上使用自定义大语言模型

作者 / 首席工程师 Cormac Brick&#xff0c;软件工程师 Haoliang Zhang 我们很高兴地发布 AI Edge Torch 生成式 API&#xff0c;它能将开发者用 PyTorch 编写的高性能大语言模型 (LLM) 部署至 TensorFlow Lite (TFLite) 运行时&#xff0c;从而无缝地将新的设备端生成式 AI 模…
阅读更多...
[大模型]Gemma-2B-Instruct FastApi 部署调用

[大模型]Gemma-2B-Instruct FastApi 部署调用

环境准备 在 平台中租赁一个 3090 等 24G 显存的显卡机器&#xff0c;如下图所示镜像选择 PyTorch-->2.1.0-->3.10(ubuntu22.04)-->12.1。 接下来打开刚刚租用服务器的 JupyterLab&#xff0c;并且打开其中的终端开始环境配置、模型下载和运行演示。 pip 换源加速下载…
阅读更多...
[qt] qt程序打包以及docker镜像打包

[qt] qt程序打包以及docker镜像打包

目录 一 环境准备: 1.1 qt环境 1.2 linuxdeplouqt打包工具 二 qt包发布: 2.1 搜索链接库 2.2 应用程序APP打包 2.3 发布 三 docker镜像包发布 3.1 环境准备 3.2 镜像生产脚本 3.3 加载镜像并运行docker容器 一 环境准备: qt环境linuxdeployqt打包工具docker环境 1…
阅读更多...
Python学习打卡：day01

Python学习打卡：day01

day1 笔记来源于&#xff1a;黑马程序员python教程&#xff0c;8天python从入门到精通&#xff0c;学python看这套就够了 1、Python 软件&#xff08;PyCharm&#xff09; 安装&#xff1a;在 Linux 环境下安装 Pycharm 插件&#xff1a;汉化、翻译 设置字体大小 常用快捷…
阅读更多...
【MySQL】（基础篇五） —— 排序检索数据

【MySQL】（基础篇五） —— 排序检索数据

排序检索数据 本章将讲授如何使用SELECT语句的ORDER BY子句&#xff0c;根据需要排序检索出的数据。 排序数据 还是使用上一节中的例子,查询employees表中的last_name字段 SELECT last_name FROM employees;输出结果&#xff1a; 发现其输出并没有特定的顺序。其实&#xf…
阅读更多...
【Linux】进程3——PID/PPID，父进程，子进程

【Linux】进程3——PID/PPID，父进程，子进程

在讲父子进程之前&#xff0c;我们接着上面那篇继续讲 1.查看进程 mycode.c makefile 我们在zs_108直接编译mycode.c&#xff0c;直接运行&#xff0c;然后我们转换另一个账号来查看这个进程 我们可以通过ps指令来查看进程 我们就会好奇了&#xff0c;第二行是什么&#xff…
阅读更多...
牛客热题：矩阵的最小路径和

牛客热题：矩阵的最小路径和

&#x1f4df;作者主页&#xff1a;慢热的陕西人 &#x1f334;专栏链接&#xff1a;力扣刷题日记 &#x1f4e3;欢迎各位大佬&#x1f44d;点赞&#x1f525;关注&#x1f693;收藏&#xff0c;&#x1f349;留言 文章目录 牛客热题&#xff1a;矩阵的最小路径和题目链接方法一…
阅读更多...
[数据集][目标检测]变电站火灾检测电力场景烟雾明火检测数据集VOC+YOLO格式140张2类别真实场景非PS合成

[数据集][目标检测]变电站火灾检测电力场景烟雾明火检测数据集VOC+YOLO格式140张2类别真实场景非PS合成

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;140 标注数量(xml文件个数)&#xff1a;140 标注数量(txt文件个数)&#xff1a;140 标注类别…
阅读更多...
模型 SCAMPER创新法则

模型 SCAMPER创新法则

说明&#xff1a;系列文章 分享 模型&#xff0c;了解更多&#x1f449; 模型_思维模型目录。激发创新的七步思维法。 1 SCAMPER创新法则的应用 1.1 SCAMPER应用之改进自行车设计 一家自行车制造商希望改进其自行车设计&#xff0c;以吸引更多的消费者并提高市场份额。他们决…
阅读更多...
Python chardet库：字符编码检测

Python chardet库：字符编码检测

更多Python学习内容&#xff1a;ipengtao.com 在处理文本文件时&#xff0c;字符编码问题常常会导致乱码和错误。Python的chardet库是一个功能强大的字符编码检测工具&#xff0c;能够帮助开发者自动检测文本的编码方式&#xff0c;从而正确地读取和处理文本文件。本文将详细介…
阅读更多...
⌈ 传知代码 ⌋ 【CLIP】文本也能和图像配对

⌈ 传知代码 ⌋ 【CLIP】文本也能和图像配对

&#x1f49b;前情提要&#x1f49b; 本文是传知代码平台中的相关前沿知识与技术的分享~ 接下来我们即将进入一个全新的空间&#xff0c;对技术有一个全新的视角~ 本文所涉及所有资源均在传知代码平台可获取 以下的内容一定会让你对AI 赋能时代有一个颠覆性的认识哦&#x…
阅读更多...
LLM Algorithms(1): Flash Attention

LLM Algorithms(1): Flash Attention

目录 Background Flash Attention Flash Attention Algorithm 参考 NIPS-2022: Flash Attention: Fast and Memory-Efficient Exact Attention with IO-Awareness idea&#xff1a;减少资源消耗&#xff0c;提升或保持模型性能。普通attention的空间复杂度是 --》降低到F…
阅读更多...
【PR2019】怎样批量添加转场效果及修改默认持续时间

【PR2019】怎样批量添加转场效果及修改默认持续时间

一&#xff0c;设置“交叉溶解”效果到所有素材 选择效果&#xff0c;右击“将所选过渡设置为默认过渡”&#xff1a; 框选所有素材&#xff0c;“Ctrl D”&#xff1a; 每个素材中间有有了交叉溶解的效果&#xff1a; 二&#xff0c;修改效果属性 2.1&#xff0c;单个修…
阅读更多...
最新文章

Copyright @ 2022~2023