算法笔记--滑动窗口

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

力扣209.长度最小子数组
https://leetcode.cn/problems/minimum-size-subarray-sum/

在这道题中要注意的不仅仅是滑动窗口的问题,更重要的问题是在循环控制中,不恰当的语法使用会导致这道题出现很严重的问题,这导致我做这道题做了很多天,真的很崩溃。

代码问题

先来看一下循环的控制问题,下面是我之前的错误代码实例:

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, right = 0;
        int sum = 0;
        int retsize = 0;
        while(right < nums.size())
        {
            if(sum < target)
                sum += nums[right++];
            else
            {
                int size = right - left;
                if(retsize == 0 || retsize > size)
                    retsize = size;
                if(sum > target)
                {
                    while(sum >= target)
                        sum -= nums[left++];
                    int size = right - left + 1;
                    if(retsize > size)
                        retsize = size;
                }
            }
        }
        if(sum > target)
        {
            while(sum >= target)
                sum -= nums[left++];
            int size = right - left + 1;
            if(retsize > size)
                retsize = size;
        }
        return retsize;
    }
};

emmmm,之前写的代码中最主要的问题就在使用while循环的同时,right的移动是在满足条件之后才可以移动,这会导致代码变得非常混乱。
所以在写代码的过程中,最好要保证一个变量是随着循环规律性发生变换,而出些需要特殊处理的情况的时候,再对其进行特殊处理,尽可能保证代码不会很乱而造成越界或者边界的控制问题。
所以修改后的代码如下:

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, right = 0;
        int sum = 0;
        int retsize = 0;
        while(right < nums.size())
        {
            sum += nums[right++];
            if (sum >= target)
            {
                while (sum >= target)
                {
                    int size = right - left;
                    if (retsize == 0 || retsize > size)
                        retsize = size;
                    sum -= nums[left++];
                }
            }
        }
        return retsize;
    }
};

滑动窗口问题

滑动窗口问题其实很简单,就上面这道题而言,如果讲这道题设计为暴力枚举的解法,那么时间复杂度为O(n^2),但本质上我们可以利用单调性规避很多没必要的枚举行为:
算法笔记--滑动窗口

起始位置时,right和left两个指针指向同一个位置,left为左边界,right为右边界,之后移动右边界并记录边界范围内的值的总和。
算法笔记--滑动窗口

当right移动到这个位置的时候,范围内的数据总和已经超过target(7),那么right继续向后移动,必定会导致在符合大于target值的基础上而这个范围在继续扩大。那么就可以确定不需要移动right,但是此时总和已经大于target了,所以接下来就要移动left,但是每次移动我们并不知道移动之后是否还满足条件,所以要进行循环判断。

代码就不贴了,上面有可以参考。这道题看起来很简单,但最主要的是循环控制问题,切忌在循环体中使用条件控制循环变量的增减,否则会导致边界很难控制。另外就是滑动窗口问题,滑动窗口利用了单调性,规避了很多没必要的枚举,这是滑动窗口的核心,它决定了哪些题目可以使用滑动窗口,哪些不可以。文章来源地址https://www.toymoban.com/news/detail-515437.html

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

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

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

相关文章

  • 滑动窗口实例1(长度最小的子数组)

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

    2024年02月11日
    浏览(33)
  • 【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日
    浏览(41)
  • 力扣精选算法100题——水果成篮(滑动窗口专题)

    本题链接👉水果成篮 我就按照实例1来进行对这题的理解。 1代表种类类型,这个数组里面有2个种类类型 ps:种类1和种类2 ,只不过种类1是有2个水果,种类2有一个水果,共计3个水果。 本题需要解答:收集水果的最大数目. 但是前提条件: 我们只有2个篮子,每个篮子里只能装

    2024年01月17日
    浏览(41)
  • 【算法|数组】滑动窗口

    给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度**。**如果不存在符合条件的子数组,返回 0 。 示例 1: 示例 2: 示例 3: 暴力解法 这种做法可以很容易想到,可是谁

    2024年02月12日
    浏览(39)
  • 【滑动窗口】长度最小的子数组|无重复字符的最长子串|最大连续1的个数 III|将 x 减到 0 的最小操作数

    1. 长度最小的子数组 - 力扣(LeetCode) (1)方法一:暴力列举出所有的子数组的和 时间复杂度:O(n**2):枚举所有子数组O(n**2) (2)方法二: 利用 单调性(两个指针都不回退) ,使用\\\" 同向双指针 \\\"(其实就是 滑动窗口 )来优化 那么 滑动窗口过程 是怎么样的? 1le

    2024年03月22日
    浏览(54)
  • 每日OJ题_算法_滑动窗口⑧_力扣76. 最小覆盖子串

    目录 力扣76. 最小覆盖子串 解析及代码 76. 最小覆盖子串 - 力扣(LeetCode) 难度 困难 给你一个字符串  s  、一个字符串  t  。返回  s  中涵盖  t  所有字符的最小子串。如果  s  中不存在涵盖  t  所有字符的子串,则返回空字符串  \\\"\\\"  。 注意: 对于  t  中重复字符,

    2024年01月23日
    浏览(41)
  • 力扣精选算法100题——找到字符串中所有字母异位词(滑动窗口专题)

    本题链接👉找到字符串中所有字母异位词 给定2个字符串s和p,找到s中所有p的变位词的字串,就是p是\\\"abc\\\",在s串中找到与p串相等的字串,可以位置不同,但是字母必须相同,比如”bca\\\",\\\"bac\\\"等,都是可以被称之为变位词。最终返回与p串字母相等但排列不同的字符串的初始索引

    2024年01月19日
    浏览(67)
  • Offer必备算法_滑动窗口_八道力扣OJ题详解(由浅到深)

    目录 滑动窗口算法介绍 ①力扣209. 长度最小的子数组 解析及代码 ②力扣3. 无重复字符的最长子串 解析及代码 ③力扣1004. 最大连续1的个数 III 解析及代码 ④力扣1658. 将x减到0的最小操作数 解析及代码 ⑤力扣904. 水果成篮 解析及代码1(使用容器) 解析及代码2(开数组) ⑥

    2024年02月20日
    浏览(47)
  • 每日OJ题_算法_滑动窗口⑦_力扣30. 串联所有单词的子串

    目录 力扣30. 串联所有单词的子串 解析及代码 30. 串联所有单词的子串 - 力扣(LeetCode) 难度 困难 给定一个字符串  s   和一个字符串数组  words 。   words  中所有字符串  长度相同 。   s   中的  串联子串  是指一个包含   words  中所有字符串以任意顺序排列连接起来的

    2024年01月21日
    浏览(45)
  • 【动态规划】【滑动窗口】【C++算法】 629K 个逆序对数组

    视频算法专题 动态规划汇总 C++算法:滑动窗口总结 逆序对的定义如下:对于数组 nums 的第 i 个和第 j 个元素,如果满足 0 = i j nums.length 且 nums[i] nums[j],则其为一个逆序对;否则不是。 给你两个整数 n 和 k,找出所有包含从 1 到 n 的数字,且恰好拥有 k 个 逆序对 的不同的数

    2024年01月17日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包