滑动窗口——优选算法

news/2024/10/4 8:10:33/

个人主页:敲上瘾-CSDN博客

个人专栏:游戏、数据结构、c语言基础、c++学习、算法

目录

一.滑动窗口算法原理:

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

1.题目解析​编辑

2.算法原理

3.代码编写

三.长度最小的子数组

1.题目解析

2.算法原理

3.代码编写

四.最小覆盖子串

1.题目解析

2.算法原理

3.代码编写

五.总结


一.滑动窗口算法原理:

        滑动窗口可以说是一种特殊双指针算法,即它同样用两个指针实现。滑动窗口:用一个left指针和right指针来维护一段区间即[left, right],也可称为窗口,right右移即进窗口,left右移即出窗口。即通常情况下left和right指针都是同向移动的。对于滑动窗口我们主要关心以下几点:

进窗口,出窗口,更新结果。进窗口肯定是在出窗口前进行的,而什么时候更新结果因题而异。

        其实对于滑动窗口本身还是挺简单的,难点在我们能不能想到使用滑动窗口,接下来我准备了三个题,每题都分为三个步骤:题目解析,算法原理,代码编写。从最普通的暴力解法过渡到滑动窗口。最后来做总结。

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

1.题目解析

        该题需要我们求出字符串s内无重复字符的最长子串,注意这里子串的意思也就是在字符串s内连续的一段字符,所以在求解该题时最好不要对原字符串进行改动。

2.算法原理

        明显这道题很容易想到的就是暴力枚举,但是时间复杂度比较高是过不了该题的测试的。在我们没能想到其他解法时,可以这样做,去分析暴力解法,从暴力解法中找到优化的规律。如下:

按以上方法把整个数组遍历完可以解决这个题目,但可以做以下优化:

        这就是一个滑动窗口,把[left, right]区间当作一个窗口存放的是不重复的子串,然后用一个len变量来记录窗口的最大长度,当right滑动到字符串结尾时也就把所有的情况都记录了一遍,此时结束循环返回len该算法就完成了。

        注意:这里因为要检查字符是否重复所以用一个哈希表来记录窗口内数据出现的个数可以提高效率。

3.代码编写

class Solution 
{
public:int lengthOfLongestSubstring(string s) {if(s.size()==0) return 0;int len=-1;int arr[127]={0};for(int left=0,right=0;right<s.size();right++){arr[s[right]]++;cout<<arr[s[right]]<<' ';while(arr[s[right]]==2){arr[s[left++]]--;}if(len<right-left+1) len=right-left+1;}return len;}
};

三.长度最小的子数组

1.题目解析

        本题要求子数组(即数组内的一段连续的元素)的元素之和大于等于target的最小长度,如果不存在返回0。例如示例1,[2,3,1,2,4,3]中子数组大于等于target的子数组有:

[2,3,1,2],[2,3,1,2,4],[2,3,1,2,4,3],[3,1,2,4],

[3,2,1,4,3],[1,2,4],[1,2,4,3],[2,4,3],[4,3]。

而长度最小的子数组为[4,3],长度为2,以上所列的子数组是一个模拟暴力枚举的结果

2.算法原理

        该题可以使用暴力枚举(即两个循环解决)时间复杂度为O(N^2)。对于暴力解法在这里就不再多讲,现在我们可以试图从暴力解法中寻找规律并进行优化。如下:

        以上我们分析的结果就是一个滑动窗口算法,left,right来维护这个窗口,left右移即出窗口,right右移即进窗口,当窗口里的元素之和大于等于target时更新最小长度。直到right滑动到数组结尾可得到答案。时间复杂度为O(N)。

3.代码编写

class Solution 
{
public:int minSubArrayLen(int target, vector<int>& nums) {int left=0,right=0;int sum=0,len=0;while(right<nums.size()){sum+=nums[right];//进窗口while(sum>=target){int ln=right-left+1;//计算窗口长度if(len==0||len>ln) len=ln;//更新lensum-=nums[left++];//出窗口}right++;}return len;}
};

四.最小覆盖子串

1.题目解析

        题目意思是给一个字符串s和t,要求在字符串s中找一个子串,这个子串要满足两点:(1)涵盖t字符串里的所有字符(包括重复字符),(2)最短的一个子串。注意:这个子串的要求不是涵盖t字符串,而是涵盖t字符串中的所有字符,这两者是有区别的。如示例1到3。

2.算法原理

        同样这题也是可以使用暴力枚举的,我们还是从暴力枚举中去寻找规律并优化。

        分析到此处,我们可以发现解题思路和上题可以说几乎是一模一样,但该题真正的难点并不是在此处。而在于我们如何去判断子串中是否包含t中的所有字符

        因为这里对子串中t的字符并没每有顺序要求,只要个数对上就行了,所以我们很自然地可以想到使用哈希表(此题使用数组充当哈希表更为高效)来记录数据出现个数。具体怎么判断呢?

        使用两个哈希表分别记录t中的字符以及个数和子串(窗口)中字符以及出现个数。然后使用遍历的方式去匹配并判断。这样确实行得通,不过涉及遍历时间复杂度一下子就上来了。在这里我给大家分享一个小技巧,是官方题解上没有的。同样我们用这两个哈希表,但不用遍历去匹配判断,而是使用一个count变量记录子串(窗口)中有效字符的个数

进窗口:当子串中某字符的个数与t字符串中对应字符个数相等时(用哈希表判断),有效字符count++。

更新结果并出窗口:当count等于t中的字符种类数时,判断并更新结果,当出窗口的元素为有效元素时(哈希表判断)count--。

3.代码编写

class Solution
{
public:string minWindow(string s, string t){string str;//储存最终结果if(s.size()<t.size()) return str;int hash1[128],hash2[128];int len=0;for(auto ch:t) if(hash1[ch]++==0) len++;int minlen=INT_MAX,begin=-1;//minlen记录最小子串长度,begin记录子串开始的位置for(int left=0,right=0,count=0;right<s.size();right++){char in=s[right];hash2[in]++;if(hash2[in]==hash1[in]) count++;while(count==len)//更新并出窗口{if(right-left+1<minlen){minlen=right-left+1;begin=left;}char out=s[left];if(hash2[out]==hash1[out]) count--;hash2[out]--;left++;   }}if(begin==-1) return "";return s.substr(begin,minlen);}
};

五.总结

        相对于暴力解法而言滑动窗口本质其实是减少不必要的枚举,那么当我们做题时一眼看不出可以使用滑动窗口或者知道要使用滑动窗口但不知道如何用的时候,我们就可以从暴力枚举的角度出发,从暴力中的寻找规律并优化。

1.滑动窗口算法的使用场景

1.1.连续子数组问题
        (1)固定窗口大小:例如,给定一个数组和窗口大小,求窗口内元素的和、最大值、最小值等。
        (2)可变窗口大小:例如,在一个数组中找到和为某一特定值的子数组,需要根据条件动态调整窗口的左右边界。
1.2.字符串子串问题
        例如,在一个字符串中查找包含特定字符集合的最短子串,或者判断一个字符串是否包含另一个字符串的排列等。

2.滑动窗口算法的基本步骤

2.1. 扩展窗口
        移动右指针来扩大窗口,直到窗口满足特定的条件或者达到数组/字符串的边界。在每次移动右指针时,更新窗口的状态变量。
2.2. 收缩窗口
        当窗口满足特定条件后,开始移动左指针来收缩窗口,同时继续更新窗口的状态变量。收缩窗口的过程是为了找到满足条件的最小窗口或者统计所有满足条件的窗口。
2.3. 更新结果
        根据窗口的状态和问题的要求,更新最终的结果,结果可能是窗口的大小、窗口内元素的某种统计值等。
 
  


http://www.ppmy.cn/news/1524531.html

相关文章

太能装了,国内有没有二本恋综?

9月&#xff0c;国内头部恋综IP节目《心动的信号第七季》开播。然而&#xff0c;与恋爱甜度相比&#xff0c;嘉宾们的“装”感却率先成为了舆论焦点。 事件起因为首集嘉宾初次会面时&#xff0c;为塑造精英形象太过刻意的行为举止。 其中&#xff0c;最具代表性的场景来自于&…

JDBC详细知识点和操作

javaweb的作用&#xff0c;属于中间者&#xff0c;负责逻辑处理 这三部分互相协作组成了网页 javaweb也就是这三部分 一.数据库部分&#xff08;略&#xff09; 二.javaweb程序 1.JDBC 概念&#xff1a;通过java代码操作数据库 数据库种类有很多&#xff0c;比如Oracle&a…

爬虫3:re正则表达式获取数据

在上一章中&#xff0c;我们基本上掌握了抓取整个网页的基本技能.但是呢&#xff0c;大多数情况下&#xff0c;我们并不需要整个网页的内容,只是 需要那么一小部分&#xff0c;怎么办呢&#xff1f;这就涉及到了数据提取的问题. 本课程中&#xff0c;提供三种解析方式&#xff…

【2025】基于Python的空气质量综合分析系统的设计与实现(源码+文档+调试+答疑)

博主介绍&#xff1a; ✌我是阿龙&#xff0c;一名专注于Java技术领域的程序员&#xff0c;全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师&#xff0c;我在计算机毕业设计开发方面积累了丰富的经验。同时&#xff0c;我也是掘金、华为云、阿里云、InfoQ等平台…

Excel如何设置不能复制里面内容?学学工作表保护功能

大家好&#xff0c;这里是效率办公指南&#xff01; &#x1f4ca; 在这个信息爆炸的时代&#xff0c;数据安全变得尤为重要。Excel文件中的数据往往包含了敏感信息&#xff0c;如何确保这些数据不被未经授权的人复制&#xff0c;成为了我们日常工作中的一个挑战。今天&#x…

【Linux 从基础到进阶】Ansible自动化运维工具使用

Ansible自动化运维工具使用 Ansible 是一款开源的自动化运维工具,采用无代理架构(agentless),基于 SSH 连接进行管理,具有简单易用、灵活强大、可扩展性高等特点。它广泛用于服务器管理、应用部署、配置管理等任务。本文将介绍 Ansible 的安装、基本使用方法及一些实际运…

uniapp+vue3实现小程序和h5解压线上压缩包以及如何访问解压后的视频地址

安装jszip插件 npm install jszip 对应功能实现和逻辑处理&#xff1a; <script setup>import { onMounted, reactive, ref } from vueimport { onHide, onUnload } from dcloudio/uni-appimport JSZip from jsziplet videoSrc ref() // 视频地址// 创建JSZip实例con…

基于 PyTorch 和 TensorFlow 的口罩检测与人脸识别系统

在后疫情时代&#xff0c;口罩检测成为了人脸识别系统的一个重要功能。如何在戴口罩的情况下准确识别身份&#xff0c;是一个技术难点。本文将介绍如何利用 PyTorch 和 TensorFlow 实现一个包含口罩检测功能的简单人脸识别系统&#xff0c;结合了Facenet 模型用于特征提取&…