【Leetcode每日一刷】滑动窗口:209.长度最小的子数组

一、209.长度最小的子数组

1.1:题目

题目链接
在这里插入图片描述

1.2:解题思路

  • 题型滑动窗口;时间复杂度:O(n)
    🪧 滑动窗口本质也是双指针的一种技巧,特别适用于字串问题

  • ❗❗核心思想/ 关键左右指针滑窗口,一前一后齐头进。
    详细思路建议看前一篇:【Leetcode每日一刷】数组|双指针篇:977. 有序数组的平方、76. 最小覆盖子串(附滑动窗口法详解)

  • 算法框架:注意下面框架中的6个关键点!

    /* 滑动窗口算法框架 */
    void slidingWindow(string s) {
        // ⭐1)用合适的数据结构记录窗口中的数据情况(以便和所需的可行解进行比对)
        unordered_map<char, int> window;
        
        // ⭐2)// 记录最小符合条件子串的起始索引及长度
    	int start = 0, len = INT_MAX; //根据实际算法所需答案进行调整
        
        int left = 0, right = 0;
        while (right < s.size()) {
            // c 是将移入窗口的字符
            char c = s[right];
            window.add(c)
            // 增大窗口
            right++;
            // ⭐3)进行增大窗口后,更新关于记录当前窗口内数据情况的变量(以便稍后和所需的可行解进行比对)
            ...
    
            /*** debug 输出的位置 ***/
            // 注意在最终的解法代码中不要 print
            // 因为 IO 操作很耗时,可能导致超时
            printf("window: [%d, %d)\n", left, right);
            /********************/
            
            // ⭐4)找到可行解——判断左侧窗口是否要收缩(进行更新)
            while (left < right && window needs shrink) {
            	//进入到这个while里面说明找到一个可行解
    			//⭐5)进行最终的所需的答案更新
    			// eg:在这里更新符合条件的*最小*子串(即最终结果)
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // d 是将移出窗口的字符
                char d = s[left];
                window.remove(d)
                // 缩小窗口
                left++;
                // ⭐6)进行缩小窗口后,更新关于记录当前窗口内数据情况的变量(以便稍后和所需的可行解进行比对)
                ...
            }
        }
    }
    
    

    🌟1. 3)6)的操作分别是扩大和缩小窗口后的更新操作,等会你会发现它们操作是完全对称的。作用都是更新当前窗口中的数据情况,再拿去和题目所需的可行解进行比对,判断当前窗口内的情况是否可行!

    🌟2. 5)步也很关键,它的作用是:找到一个可行解&更新得到一个可行解后,对题目最终需要的最优答案进行更新!

  • 本题思路(依据算法框架)

    1. ⭐首先设置一个记录当前窗口情况的变量windowSum(作用是方便与所需可行条件进行比较)——记录当前窗口中元素综合
    2. ⭐设置存储最终答案(窗口长度)的变量(作用是得到可行情况后,进行实时更新,以得到最终的最优答案)
    3. ⭐设置leftright指针对窗口大小进行控制
    4. ⭐在窗口的增大和缩小过程中实时更新记录当前窗口情况的变量windowSum
    5. ⭐在得到可行解的情况下,实时更新最终答案

1.3:实现代码——c++

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
            //设置一个记录当前窗口情况的变量(即当前窗口内元素总和
            int windowSum = 0;
            //算法的最终答案:minLen
            int minLen = INT_MAX;
            int left =0, right = 0;
            while(left <= right && right < nums.size()){
                //先记下窗口待新增元素
                int a = nums[right];
                right++;
                //增大窗口后,更新当前窗口中的情况
                windowSum += a;

                while(left <= right && windowSum >= target){
                    //首先,因为进入循环就代表得到哦一个可行结果,立马更新答案
                    minLen = min(minLen, right - left);
                    //先记下窗口待减少元素
                    int b = nums[left];
                    left++;
                    //窗口减小后,更新记录当前窗口的元素
                    windowSum -= b;
                }
            }
            return minLen == INT_MAX ? 0 : minLen;
    }
};

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

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

相关文章

A5自媒体wordpress主题模板

一个简洁的wordpress个人博客主题&#xff0c;适合做个人博客&#xff0c;SEO优化效果挺不错的。 https://www.wpniu.com/themes/204.html

前端学习之行内和块级标签

行内标签 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>span</title> </head> <body><!-- 行内标签特点&#xff1a;1、不换行,一行可以放多个2、默认宽度内容撑开代表&#…

谈谈我的自媒体创作真实感悟

因为我有数十款APP和小程序&#xff0c;基本都是些辅助内容创作的工具&#xff0c;于是我就顺水推舟做了几个自媒体账号&#xff1a;微信公众号&#xff0c;抖音&#xff0c;知乎&#xff0c;小红书&#xff0c;CSDN等&#xff0c;账号的名字都是全赞工程师。 目前这些号有收入…

分享一些实用性的大语言模型(GitHub篇)

1.多模态大模型 GitHub网址&#xff1a;haotian-liu/LLaVA&#xff1a;[NeurIPS23 Oral] 视觉指令调优 &#xff08;LLaVA&#xff09; 构建&#xff0c;旨在实现 GPT-4V 级别及以上的能力。 (github.com) 下面是LLaVA模型的介绍&#xff0c;作者都有一直维护和更新&#xff0c…

CSS居中对齐 (垂直居中)

内部块级元素的高度要小于容器(父元素) 方案一&#xff1a;行高 容器高度&#xff08;单行内联元素&#xff09; 限制条件&#xff1a;仅用于单行内联元素 display:inline 和 display: inline-block; 给容器添加样式 height: 100px;line-height: 100px;<!DOCTYPE html>…

TimescaleDB 开源时序数据库

文章目录 1.TimescaleDB介绍2.Hypertable 和 chunk3.Hypertable4.Hypertable操作 开源中间件 # TimescaleDBhttps://iothub.org.cn/docs/middleware/ https://iothub.org.cn/docs/middleware/timescale/timescale-summary/1.TimescaleDB介绍 TimescaleDB是基于PostgreSQL数据…

MATH数据集分享

来源: AINLPer公众号&#xff08;每日干货分享&#xff01;&#xff01;&#xff09; 编辑: ShuYini 校稿: ShuYini 时间: 2024-3-10 很多创新性的研究都可能会遇到数学问题&#xff0c;但是这项技能对于计算机来说仍然是个不小的挑战。为了衡量模型在解决数学问题上的表现。UC…

C++11的简单介绍(上)

1.C11简介 在2003年C标准委员会曾经提交了一份技术勘误表(简称TC1)&#xff0c;使得C03这个名字已经取代了C98称为C11之前的最新C标准名称。不过由于C03(TC1)主要是对C98标准中的漏洞进行修复&#xff0c;语言的核心部分则没有改动&#xff0c;因此人们习惯性的把两个标准合并…

Go语言必知必会100问题-20 切片操作实战

前言 有很多gopher将切片的length和capacity混淆&#xff0c;没有彻底理清这两者的区别和联系。理清楚切片的长度和容量这两者的关系&#xff0c;有助于我们合理的对切片进行初始化、通过append追加元素以及进行复制等操作。如果没有深入理解它们&#xff0c;缺少高效操作切片…

一文彻底搞懂MyISAM和InnoDB区别

文章目录 1. 是否支持行级锁2. 是否支持事务3. 是否支持外键4. 是否支持数据库异常崩溃后的安全恢复5. 是否支持 MVCC6. 索引实现7. 常见的几种 MySQL 存储引擎对比 MySQL 5.5版本之前&#xff0c;MyISAM引擎是MySQL的默认存储引擎&#xff0c;拥有全文索引、压缩和空间函数等特…

力扣——合并k个升序链表

文章目录 题目解析题目链接题目解析 算法讲解暴力解法利用优先级队列进行优化 代码解析 题目解析 题目链接 首先先把题目连接给大家奉上题目链接 题目解析 严格来说这个题目是非常容易理解的相信大家有了合并两个升序链表来理解这个题目就会非常容易理解了。这个题目的意思就…

LeetCode 654.最大二叉树

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建: 创建一个根节点&#xff0c;其值为 nums 中的最大值。 递归地在最大值 左边 的 子数组前缀上 构建左子树。 递归地在最大值 右边 的 子数组后缀上 构建右子树。 返回 nums 构建的 最大二叉树…

Spring Security | Oauth2 /oauth/token自定义授权实现底层源码浅析与实现

Spring Security Oauth2 /oauth/token自定义授权源码分析实现过程&#xff0c;看了网上很多文章&#xff0c;分析和实现肯定存在不完整地方&#xff0c;可以在评论区指出交流。 1 /oauth/token入口 org.springframework.security.oauth2.provider.endpoint.TokenEndpoint Token…

java的参数传递机制(引用类型)

1.除了非引用类型的形参传递&#xff0c;还有引用类型的变量形参传递&#xff0c;但引用类型的形参变量传递与非引用类型是不同的&#xff01;&#xff01;&#xff01; public class MethodDemo2 {public static void main(String[] args) {int[] arr new int[]{10,20,30,9}…

MySQL入门到中级知识汇总2024

文章目录 1.揭开MySQL的神秘面纱2. SQL的基本命令实操3. 数据库的备份与恢复4. MySQL常用的数据类型&#xff08;列类型&#xff09;5. 数据类型之小数类型的使用6. 表的创建7. 表的修改8. mysql事务9. mysql表类型和存储引擎10. mysql的视图11. mysql的管理 1.揭开MySQL的神秘…

20.2 nginx

20.2 nginx 1. 学习目标2. 介绍2.1 正向代理2.2 反向代理2.3 动态静态资源分离2.4 nginx优缺点3. 安装3.1 Linux安装****************************************************************************************************************************************************…

Charles-抓包工具的使用

文章目录 Charles简介与安装Charles的简介Charles的安装Charles 安装证书 抓包在PC端抓取HTTPS请求在移动端进行抓包移动端配置Androd端配置iOS端配置 Charles使用小技巧&#xff1a; 模拟慢速网络 Charles简介与安装 Charles的简介 Charles 是在 PC 端常用的网络封包截取工具…

块设备驱动(1)-什么是块设备驱动?块设备驱动概念总结

1.块设备驱动概念 块设备驱动是针对存储设备&#xff0c;例如SD卡、EMMC、NAND FLASH、NOR FLSASH。 块设备驱动以块为单位进行访问、最小寻址单位是扇区、一个块中包含多个扇区、支持随机访问、带缓冲区&#xff0c;&#xff0c;当发生写入操作时&#xff0c;并不会立马操作硬…

GPU,一统天下

三十年前&#xff0c;CPU 和其他专用处理器几乎处理所有计算任务。那个时代的显卡有助于加快 Windows 和应用程序中 2D 形状的绘制速度&#xff0c;但没有其他用途。 快进到今天&#xff0c;GPU 已经成为业界最具主导地位的芯片之一。 但具有讽刺意味的是&#xff0c;图形芯片…

checking file system on C

1、win7系统 开机检查C盘&#xff0c;虽然可以ESC取消检查&#xff0c;每次操作很麻烦&#xff0c;且没有意思 2、注册表清空BootExecute数值数据 1&#xff09;打开注册表 WinR &#xff08;快捷键&#xff09;输入“regedit”&#xff0c;回车 2&#xff09;位置HKEY_LOCAL…