【优选算法】9----长度最小的子数组

----------------------------------------begin--------------------------------------

铁子们,前面的双指针算法篇就算告一段落啦~

接下来是我们的滑动窗口篇,不过有一说一,算法题就跟数学题一样,只要掌握方法,多做题,还

是差不多可以解决的,当然,我说的是差不多哦~

接下来就让我们迎接滑动窗口这一类算法的学习吧!

题目解析:

重点:在学习滑动窗口这一类算法题前,我们需要了解一个概念:“滑动窗口”是什么?

我们来用寻宝藏来设想一下:

滑动窗口就像是一个会自动调整大小的“魔法窗口”,在数组上滑动,寻找宝藏。它能大大减少不必要的计算,效率比暴力解法高多了。

讲解算法原理:

方法一:暴力解法:简单粗暴的大搜索

这题的解题思路就像是找宝藏,一开始咱两眼一抹黑,不知道宝藏在哪,那就得从最开始的地方一

点点摸索。

暴力解法很直接,就是把所有可能的子数组都找出来,计算它们的和,看看哪个子数组的和大于等

于 target ,然后找出其中长度最小的。这就好比把整个森林里的每一个角落都翻个遍,肯定能找

到宝藏,但就是有点费时间和精力。

方法二:聪明的寻宝法

这里的 left 和 right 就是滑动窗口的左右边界。一开始,窗口大小为 0 ,也就是 left 和 right 都在

数组的起始位置。然后,right 开始向右移动,就像把窗口一点点扩大,把新的数字装进窗口里,

同时累加窗口内数字的和。当窗口内数字的和大于等于 target 时,就说明找到了一个可能的“宝藏

序列”,这时候就尝试把窗口左边的边界 left 向右移动,看看能不能把窗口缩小,同时保持和大于

等于 target 。每缩小一次,就更新一下最小长度。这样不断地滑动窗口,就能找到满足条件的最

小子数组长度啦。

滑动窗口的时间复杂度是 O(n) ,因为每个元素最多进窗口和出窗口各一次,效率比暴力解法高了

不知道多少倍,就像开着跑车在森林里找宝藏,又快又准!

编写代码:

方法二如下所示:

​
​
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n=nums.size(),sum=0,len=INT_MAX;for(int right =0,left=0;right<n;right++){sum+=nums[right];while(sum>=target){len=min(len,right-left+1);sum-=nums[left++];}}return len==INT_MAX?0:len;}
};​​

这道长度最小的子数组题目,通过暴力解法和滑动窗口两种思路的对比,让我们看到了算法优化的

魅力。暴力解法虽然简单易懂,但在效率上输给了滑动窗口。就像生活中,有时候简单直接的方法

虽然能解决问题,但多花点心思,找到更巧妙的方法,往往能事半功倍。

希望大家都能学会这个滑动窗口的技巧,以后再遇到类似的问题,就能轻松解决啦!

题目直达---->

209. 长度最小的子数组 - 力扣(LeetCode)

-------------------------------------------end-------------------------------------

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

计算机网络之链路层

本文章目录结构出自于《王道计算机考研 计算机网络_哔哩哔哩_bilibili》 02 数据链路层 在网上看到其他人做了详细的笔记&#xff0c;就不再多余写了&#xff0c;直接参考着学习吧。 1 详解数据链路层-数据链路层的功能【王道计算机网络笔记】_wx63088f6683f8f的技术博客_51C…

Kubernetes v1.28.0安装dashboard v2.6.1(k8s图形化操作界面)

准备工作 Kubernetes v1.28.0搭建教程请参考&#xff1a;Kubernetes v1.28.0集群快速搭建教程-CSDN博客 查看当前集群nodes都是ready状态 查看当前pods都是running状态 下载并修改配置文件 下载 recommended.yaml &#xff0c;下载好之后&#xff0c;进入文件编辑 下载地址…

Spring 框架:配置缓存管理器、注解参数与过期时间

在 Spring 框架中&#xff0c;可通过多种方式配置缓存具体行为&#xff0c;常见配置方法如下。 1. 缓存管理器&#xff08;CacheManager&#xff09;配置 基于内存的缓存管理器配置&#xff08;以SimpleCacheManager为例&#xff09; SimpleCacheManager 是 Spring 提供的简单…

2025.1.21——六、BUU XSS COURSE 1 XSS漏洞|XSS平台搭建

题目来源&#xff1a;buuctf BUU XSS COURSE 1 目录 一、打开靶机&#xff0c;整理信息 二、解题思路 step 1&#xff1a;输入框尝试一下 step 2&#xff1a;开始xss注入 step 3&#xff1a;搭建平台 step 4&#xff1a;利用管理员cookie访问地址 三、小结 二编&#…

基于Python机器学习的双色球数据分析与预测

python统计分析2003-2024年所有的中奖记录,通过人工智能机器学习预测双色球,个人意见,仅供参考. 声明&#xff1a;双色球具有随机性&#xff0c;任何工具无法预测。本文章仅作为技术交流&#xff0c;提供学习参考。本文所涉及的代码均为python之机器学习的代码。双色球为公益事…

警企联动齐发力、共筑反诈“防护墙”

2025年1月10日是第五个中国人民警察节,南通移动联合南通公安反诈中心,深入社区商圈,开展防范电信网络诈骗宣传活动,进一步增强广大人民群众的反诈意识和能力,全力守护好群众的“钱袋子”。 当日,活动现场一大早就呈现出一片忙碌景象,工作人员支起摊位,将各类精心制作的反诈宣传…

mysql 学习3 SQL语句--整体概述。SQL通用语法;DDL创建数据库,查看当前数据库是那个,删除数据库,使用数据库;查看当前数据库有哪些表

SQL通用语法 SQL语句分类 DDL data definition language : 用来创建数据库&#xff0c;创建表&#xff0c;创建表中的字段&#xff0c;创建索引。因此成为 数据定义语言 DML data manipulation language 有了数据库和表以及字段后&#xff0c;那么我们就需要给这个表中 添加数…

九、CSS工程化方案

一、PostCSS介绍 二、PostCSS插件的使用 项目安装 - npm install postcss-cli 全局安装 - npm install postcss-cli -g postcss-cli地址&#xff1a;GitHub - postcss/postcss-cli: CLI for postcss postcss地址&#xff1a;GitHub - postcss/postcss: Transforming styles…

Baklib助力企业如何搭建内容中台的全新策略解析

内容概要 在当今快速变化的商业环境中&#xff0c;企业面临着数据爆炸和信息管理的巨大挑战。内容中台作为一种新兴的管理理念&#xff0c;专注于内容的集中管理与高效利用&#xff0c;旨在帮助企业优化信息流动&#xff0c;提高工作效率。通过构建一个灵活、可扩展的内容中台…

AR智慧点巡检系统探究和技术方案设计

一、项目背景 随着工业生产规模的不断扩大和设备复杂度的提升&#xff0c;传统的人工点巡检方式效率低下、易出错&#xff0c;难以满足现代化企业对设备运行可靠性和安全性的要求。AR&#xff08;增强现实&#xff09;技术的发展为点巡检工作带来了新的解决方案&#xff0c;通…

LabVIEW项目中的工控机与普通电脑选择

工控机&#xff08;Industrial PC&#xff09;与普通电脑在硬件设计、性能要求、稳定性、环境适应性等方面存在显著差异。了解这些区别对于在LabVIEW项目中选择合适的硬件至关重要。下面将详细分析这两种设备的主要差异&#xff0c;并为LabVIEW项目中的选择提供指导。 ​ 硬件设…

计算机图形学:实验四 带纹理的OBJ文件读取和显示

一、程序功能设计 在程序中读取带纹理的obj文件&#xff0c;载入相应的纹理图片文件&#xff0c;将带纹理的模型显示在程序窗口中。实现带纹理的OBJ文件读取与显示功能&#xff0c;具体设计如下&#xff1a; OBJ文件解析与数据存储 通过实现TriMesh类中的readObj函数&#x…

C# OpenCV机器视觉:红外体温检测

在一个骄阳似火的夏日&#xff0c;全球却被一场突如其来的疫情阴霾笼罩。阿强所在的小镇&#xff0c;平日里熙熙攘攘的街道变得冷冷清清&#xff0c;人们戴着口罩&#xff0c;行色匆匆&#xff0c;眼神中满是对病毒的恐惧。阿强作为镇上小有名气的科技达人&#xff0c;看着这一…

PAT甲级-1020 Tree Traversals

题目 题目大意 给出一棵树的后序遍历和中序遍历&#xff0c;要求输出该树的层序遍历。 思路 非常典型的树的构建与遍历问题。后序遍历和中序遍历可以得出一个树的结构&#xff0c;用递归锁定根节点&#xff0c;然后再遍历左右子树&#xff0c;我之前发过类似题目的博客&…

C语言进阶——3字符函数和字符串函数(2)

8 strsrt char * strstr ( const char *str1, const char * str2);查找子字符串 返回指向 str1 中第一次出现的 str2 的指针&#xff0c;如果 str2 不是 str1 的一部分&#xff0c;则返回 null 指针。匹配过程不包括终止 null 字符&#xff0c;但会在此处停止。 8.1 库函数s…

python学opencv|读取图像(四十二)使用cv2.add()函数实现多图像叠加

【1】引言 前序学习过程中&#xff0c;掌握了灰度图像和彩色图像的掩模操作&#xff1a; python学opencv|读取图像&#xff08;九&#xff09;用numpy创建黑白相间灰度图_numpy生成全黑图片-CSDN博客 python学opencv|读取图像&#xff08;四十&#xff09;掩模&#xff1a;三…

基于C语言的数组从入门到精通

简介:本篇文章主要介绍了一维数组,二维数组,字符数组的定义,数组的应用,数组的核心代码解析,适用于0基础的初学者. C语言数组 1.一维数组 1.1定义 1.1.1声明 语法:数据类型 数组名[数组大小];示例:int arr[5]; 1.1.2初始化 a.静态初始化 完全初始化&#xff1a;int arr[5] {1…

【kong gateway】5分钟快速上手kong gateway

kong gateway的请求响应示意图 安装 下载对应的docker 镜像 可以直接使用docker pull命令拉取&#xff0c;也可以从以下地址下载&#xff1a;kong gateway 3.9.0.0 docker 镜像 https://download.csdn.net/download/zhangshenglu1/90307400&#xff0c; postgres-13.tar http…

python 安装插件 requests 下载免费简历(自学7)

安装 requests 库&#xff1a; 他们三个 按一个就行 pip install requests 或者 pip3 install requests 或者 conda install requests 代码 每次只可以下载一页的 简历模板 需要手动修改 id ### import requests from lxml import etree import osif __name__ "__…

西门子【Library of General Functions (LGF) for SIMATIC S7-1200 / S7-1500】

文章目录 概要整体架构流程技术名词解释技术细节小结 概要 通用函数库 (LGF) 扩展了 TIA Portal 中用于 PLC 编程的 STEP 7 指令&#xff08;数学函数、时间、计数器 等&#xff09;。该库可以不受限制地使用&#xff0c;并包含 FIFO 、搜索功能、矩阵计算、 astro 计…