【刷题】滑动窗口入门

这篇具有很好参考价值的文章主要介绍了【刷题】滑动窗口入门。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【刷题】滑动窗口入门,刷题,算法,c++,学习,数据库,蓝桥杯
送给大家一句话:

那脑袋里的智慧,就像打火石里的火花一样,不去打它是不肯出来的。——莎士比亚文章来源地址https://www.toymoban.com/news/detail-843446.html

今天我学习了滑动窗口的算法思路,接下来请与我一起看看吧!!!

认识滑动窗口

滑动窗口问题可以说是一种特殊的双指针问题,通常用于解决以下类型的问题:

  1. 连续子数组或子字符串问题:例如,找出一个数组中连续元素和最大或最小的子数组,或者在字符串中找到一个包含特定字符的最短子字符串。
  2. 固定窗口大小问题:当窗口大小固定时,我们可以通过移动窗口来遍历整个数组或字符串,并记录所需的统计信息。
  3. 可变窗口大小问题:在某些情况下,窗口的大小可能会根据特定条件而变化。这需要我们在遍历过程中动态地调整窗口的大小。

滑动窗口算法的基本思想是使用双指针(有时也可能使用更多指针)来表示窗口的边界。在每一步中,我们可以根据特定条件来移动窗口的边界,并更新所需的统计信息。

看这些定义是真无法想象出来哦怎么个滑动窗口的,下面我们一起来做题吧:

Leetcode 209. 长度最小的子数组

题目描述

【刷题】滑动窗口入门,刷题,算法,c++,学习,数据库,蓝桥杯
看这个题目还是很好理解的,只需要我们找到和大于target的连续子数组,我们来看第一个样例target = 7, nums = [2,3,1,2,4,3] 显然4,3是最小的子数组。接下来分析一下算法思路:

算法思路

根据题目要求,首先可以想到的是暴力枚举算法(遇事不决,暴力解决),遍历穷举出所有的连续子数组,寻找满足要求的子数组,最终就找到了最小的连续子数组:

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++) {
        //重置sum值
            int sum = 0;
            //判断子数组是否满足
            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;
    }
};

这样暴力的算法的时间复杂度是O(n^2),我们看看可不可以进行优化:
来看图解(来着力扣官方)【刷题】滑动窗口入门,刷题,算法,c++,学习,数据库,蓝桥杯

这样就模拟了滑动窗口:
做法:将右端元素划⼊窗⼝中,统计出此时窗⼝内元素的和:

  • 如果窗⼝内元素之和⼤于等于 target :更新结果,并且将左端元素划出去的同时继续判
    断是否满⾜条件并更新结果(因为左端元素可能很⼩,划出去之后依旧满⾜条件)
  • 如果窗⼝内元素之和不满⾜条件: right++ ,另下⼀个元素进⼊窗⼝。
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0,right = 0;
        //设置为最大值 保证没有满足的子数组时可以判断
        int len = INT_MAX;
        int sum = 0;
        sum += nums[left];

        while(left < nums.size() && right < nums.size()){
			//
            if(sum < target ){
                right++;
                if(right < nums.size())
                    sum += nums[right];

            }
            while (sum >= target){
                len = min (right - left + 1 , len) ;
                sum -= nums[left];
                left++;
            }
        }
        return len == INT_MAX ? 0:len;
    }
};

这样大大提高了算法的效率!!!
为何滑动窗⼝可以解决问题,并且时间复杂度更低?

  1. 这个窗⼝寻找的是:以当前窗⼝最左侧元素(记为 left1 )为基准,符合条件的情况。也就是在这道题中,从 left1 开始,满⾜区间和 sum >= target 时的最右侧(记为right1 )能到哪⾥。
  2. 我们既然已经找到从 left1 开始的最优的区间,那么就可以⼤胆舍去 left1 。但是如果继续像⽅法⼀⼀样,重新开始统计第⼆个元素( left2 )往后的和,势必会有⼤量重复的计算(因为我们在求第⼀段区间的时候,已经算出很多元素的和了,这些和是可以在计算下次区间和的时候⽤上的)。
  3. 此时, rigth1 的作⽤就体现出来了,我们只需将 left1 这个值从sum 中剔除。从right1 这个元素开始,往后找满⾜ left2 元素的区间(此时right1 也有可能是满⾜的,因为 left1 可能很⼩。 sum 剔除掉 left1 之后,依旧满⾜⼤于等于target )。这样我们就能省掉⼤量重复的计算。

这样我们不仅能解决问题,⽽且效率也会⼤⼤提升

继续我们来看下一题

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

题目描述

【刷题】滑动窗口入门,刷题,算法,c++,学习,数据库,蓝桥杯
描述也是十分简单奥,我们接着来看如何解决

算法思路

首先想到的还是暴力枚举啊,我们可以借助哈希表来确定是否重复。
枚举过程中就会发现左右指针移动方向相同,所以可以进行滑动窗口

  1. 入窗口(右指针移动)
  2. 判断(判断是否需要移动左指针)
  3. 出窗口
  4. 更新结果
class Solution {
public:

    int lengthOfLongestSubstring(string s) {
        int len = 0;
        int n = s.size();
        //使用哈希进行判断是否重复
        int hash[128] = {0};
        int ret = 0;
        for(int left = 0,right = 0; right < n; right++){
       		//进入窗口
            hash[s[right]]++;
			//判断
            while(hash[s[right]] > 1){
            	//出窗口
                hash[s[left]]--;
                left++;
                len--;
            }
      		//更新结果
            len++;
            ret = max(len,ret);
        }
        return ret;

    }
};

这样就完美解决。
其实滑动窗口都是可以套用上面的模版的,不信?来看下一题

Leetcode 1004. 最大连续1的个数 III

题目描述

【刷题】滑动窗口入门,刷题,算法,c++,学习,数据库,蓝桥杯
题目描述依然简单奥,只是判断条件发生了改变,我们需要来定义一个数字来比较是否满足少于k

算法思路

依旧是:

  1. 入窗口(右指针移动)
  2. 判断(判断是否需要移动左指针)
  3. 出窗口
  4. 更新结果
class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int tmp = 0,left = 0,right = 0,n = nums.size();
        int ret = 0;
        while(right < n){

            if(nums[right] == 0) {
                tmp++;    
            }

            while(tmp > k){
                if(nums[left] == 0) tmp--;
                left++;
            }

            ret = max(ret,right - left + 1);
            right++;
        }
        return ret;
    }
};

这样就成功完成解题!!!

总结

滑动窗口问题是可以通过模版来解决:

  1. 入窗口(右指针移动)
  2. 判断(按题分析判断是否需要移动左指针)
  3. 出窗口
  4. 更新结果

这样基本滑动窗口都可以解决,但重要的是理解滑动窗口的思路是如何得到的,是如何从暴力算法优化出来的。

送给大家一句话:

那脑袋里的智慧,就像打火石里的火花一样,不去打它是不肯出来的。——莎士比亚

Thanks♪(・ω・)ノ谢谢阅读!!!

下一篇文章见

到了这里,关于【刷题】滑动窗口入门的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

原文地址:https://blog.csdn.net/JLX_1/article/details/136854460

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 力扣刷题-队列-滑动窗口最大值

    给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。 返回滑动窗口中的最大值。 进阶: 在线性时间复杂度内解决此题? 参考:https://www.programmercarl.com/0239.%E6%BB%91%E5%8A

    2024年02月06日
    浏览(13)
  • 刷题(双指针思想/滑动窗口思想/l螺旋矩阵)

    刚开始自己做就是无脑ac的,sort: 但是时间复杂度有问题, 是O(nlogn)的时间复杂度 提升:用双指针的思想:时间复杂度为O(n) 使用 双指针 的思想解决本题的思路: 以数组 为例: 输入:nums = [-4,-1,0,3,10] 输出:[0,1,9,16,100] 因为输入的数组是递增的,因此,平方后的最大值,只

    2023年04月08日
    浏览(11)
  • 【算法&数据结构体系篇class24】:滑动窗口技巧

    滑动窗口是一种想象出来的数据结构: 滑动窗口有左边界L和有边界R 在数组或者字符串或者一个序列上,记为S,窗口就是S[L..R]这一部分 L往右滑意味着一个样本出了窗口,R往右滑意味着一个样本进了窗口 L和R都只能往右滑 窗口不管L还是R滑动之后,都会让窗口呈现新状况,

    2023年04月09日
    浏览(10)
  • 人大金仓数据库KingbaseES 安全功能入门学习

    安全、身份鉴别、用户管理、审计 金仓数据库管理系统KingbaseES V8.0支持微软Windows 7、Windows XP、Windows 2003、 Windows 2008等32位及64位发行版本。 准备需要安装的金仓数据库管理系统KingbaseES安装程序和jdk1.8及以上的jdk环境。 1.3.1 安装用户 在安装金仓数据库管理系统KingbaseES V8.0时

    2024年02月05日
    浏览(13)
  • sql_server数据库入门学习(二)

    🎬 博客主页:博主链接 🎥 本文由 M malloc 原创,首发于 CSDN🙉 🎄 学习专栏推荐:LeetCode刷题集! 🏅 欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正! 📆 未来很长,值得我们全力奔赴更美好的生活✨ ------------------❤️分割线❤️------------------------- —————————

    2024年02月08日
    浏览(10)
  • sql_server数据库入门学习(一)

    🎬 博客主页:博主链接 🎥 本文由 M malloc 原创,首发于 CSDN🙉 🎄 学习专栏推荐:LeetCode刷题集! 🏅 欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正! 📆 未来很长,值得我们全力奔赴更美好的生活✨ ------------------❤️分割线❤️------------------------- —————————

    2024年02月07日
    浏览(12)
  • 【Leetcode刷题-Python/C++】长度最小的子数组(滑动窗口)

    209.长度最小的子数组 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。 输入:target = 7, nums = [2,3,1,2,4,3] 输出:2 解释:子数

    2023年04月08日
    浏览(6)
  • 【剑指offer刷题记录 java版】数组双指针 之 滑动窗口

    本系列文章记录labuladong的算法小抄中剑指offer题目 题目链接:https://leetcode.cn/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/ 题目链接:https://leetcode.cn/problems/MPnaiL/ 题目链接:https://leetcode.cn/problems/VabMRr/ 题目链接:https://leetcode.cn/problems/wtcaE1/ 题目链接:https://leetcode.cn/pr

    2024年02月09日
    浏览(16)
  • 【leetcode刷题之路】面试经典150题(2)——双指针+滑动窗口+矩阵

    2 双指针 2.1 【双指针】验证回文串 题目地址:https://leetcode.cn/problems/valid-palindrome/description/?envType=study-plan-v2envId=top-interview-150   详见代码。 2.2 【双指针】判断子序列 题目地址:https://leetcode.cn/problems/is-subsequence/description/?envType=study-plan-v2envId=top-interview-150   双指针挨个遍

    2024年02月19日
    浏览(13)
  • 时序数据库TDengine窗口函数

    select ts, lp_index, max(lp_value),  lp_project_id, lp_variable_uri,  lp_time_ticks, lp_value_type_value, lp_value, lp_unit from weixingdata.tdm_lp_original_data where  lp_time_ticks = \\\'2023-11-27 12:38:41\\\'                 and lp_time_ticks =  \\\'2023-11-27 14:38:41\\\'       and  lp_project_id = \\\'0A66F139-F8BF-485A-9F3B-DECD40C3E6D9\\\'      and

    2024年02月20日
    浏览(14)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包