<滑动窗口> 长度最小的子数组

题目链接:209. 长度最小的子数组 - 力扣(LeetCode)

题目分析

由暴力枚举引申到滑动窗口的画图分析过程

优化版本(滑动窗口)

滑动窗口的使用场景:单调性(一定是递增或递减的情况) + 可以不回退的同向双指针(可能是int left和right,可能是是int *left和*right)

使用模板: 

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size(),sum = 0,len = INT_MAX;for(int left = 0,right = 0;right < n;right++){sum += nums[right];//进窗口while(sum >= target){len = min(len,right - left + 1);//更新结果, right-left+1表示符号条件的子数组长度sum -= nums[left++];//出窗口(如果出窗口后rigth仍然小于n就重新进窗口)}}return len == INT_MAX ? 0 : len;//需要加一个判断条件,如果没有满足的子数组应该返回0//但初始化时将len设置为INT_MAX,故如果最后len仍为INT_MAX时就返回0}
};

补充:因为当前我们只要一个最小的子数组长度,不是取所有我们统计到的满足条件的子数组的中间值的那种要求,所以不用set记录结果,直接当遇到更小的len时更新len即可,且len的初始值太小,因为如果答案的最小子数组长度为5而你len的初始值为2,那么就一直得不到正确结果,所以最好将其设置一个足够大的值比如INT_MAX

时间复杂度: O(N)

时间复杂度分析:

代码是两层循环嵌套,暴力枚举时的确是O(N^2)因为right每次还要回到left的新位置最坏情况是right每走N次返回left,left需要走N次才能到达末尾,即(N * N )= O(N^2)

但滑动窗口中的right只会接着上次的结果继续移动,且当某条件满足时left继续右移,最坏的情况就是当right移动n次到数组末尾时才满足条件,然后left才会去移动N次也到达数组末尾,即O(N + N )= O(2N)=  O(N),

问题:为什么这样就可以得到正确结果?暴力枚举是将所有结果都枚举出来然后选出符号要求的结果,滑动窗口并没有枚举出所有结果,它是如何保证正确性的?

解释:滑动窗口利用单调性,规避了很多没有必要的枚举行为,上述案例中在确定一个满足条件的子数组长度后,因为是right继续向后走sum一定会增加且一直大于target,这时还继续向后走统计出一个长度为5的子数组{2,3,1,2,4}是没有必要的,前面已经有了一个长度为4的子数组{2,3,1,2},长度为5甚至是6的子数组肯定不会是最终结果,不枚举也罢

还不懂就画一个小窗口自己套在数组上试一试

~over~

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

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

相关文章

Linux DHCP server 配置

参考&#xff1a;linux dhcp配置多vlan ip_linux 接口vlan-CSDN博客 配置静态IP地址&#xff1a; 给固定的MAC地址分配指定的IP地址&#xff0c;固定的IP地址不必包含在指定的IP池中&#xff0c;如果包含在IP地址池中&#xff0c;固定的IP地址会从IP地址池中移除 配置方法&…

YOLOV10阅读总结

GitHub - THU-MIG/yolov10: YOLOv10: Real-Time End-to-End Object Detection YOLOv10 - Ultralytics YOLO Docs https://arxiv.org/pdf/2405.14458 论文地址 最近yolo又出了个yolov10了&#xff0c;不得不感慨CV是真卷&#xff0c;毕竟yolov9也才没多久。记录一下阅读笔记。…

基于Java实现的图书管理系统

前言&#xff1a;该图书管理系统实现了查找、添加、删除、显示、借阅、归还等功能&#xff0c;分为两个用户群体&#xff1a;管理者和普通用户。使用了类与对象&#xff0c;封装继承多态&#xff0c;抽象类和接口等Java基础知识。 一.思路 面向对象三部曲&#xff1a;找对象&…

西湖大学提出AIGC检测框架,精准识别AI撰写的文稿

近年来人工智能技术突飞猛进&#xff0c;尤其是大语言模型的出现&#xff0c;让AI具备了创作文章、小说、剧本等内容的能力。 AI代写&#xff0c;已经逃不过老师、编辑、审稿人的火眼金睛了。但让AI仅改写部分片段&#xff0c;就安全了么&#xff1f; 针对检测AI改写的片段&a…

整理了六个正规靠谱的兼职赚钱软件,适合普通人做的兼职副业~

​随着互联网时代的到来&#xff0c;越来越多的人选择通过互联网赚钱。在这篇文章中&#xff0c;我们将探讨一些可以在网上长期赚钱的方法。 在网络上面其实有很多的赚钱方法&#xff0c;尽管方法很多&#xff0c;但是对于一些网络新手&#xff0c;刚进入互联网圈子不久的伙伴…

ES升级--04--SpringBoot整合Elasticsearch

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 SpringBoot整合Elasticsearch1.建立项目2.Maven 依赖[ES 官方网站&#xff1a;https://www.elastic.co/guide/en/elasticsearch/client/java-rest/6.8/index.html](…

使用python绘制一个五颜六色的爱心

使用python绘制一个五颜六色的爱心 介绍效果代码 介绍 使用numpy与matplotlib绘制一个七彩爱心&#xff01; 效果 代码 import numpy as np import matplotlib.pyplot as plt# Heart shape function def heart_shape(t):x 16 * np.sin(t)**3y 13 * np.cos(t) - 5 * np.cos…

【RabbitMQ】SpringAMQP--消息转换器

SpringAMQP–消息转换器 测试发送Object类型消息 1.声明队列 Configuration public class FanoutConfig {Beanpublic Queue objectQueue(){return new Queue("object.queue");} }运行消费者后&#xff1a; 2.发送消息 RunWith(SpringRunner.class) SpringBootTes…

POLARDB:新零售用户MySQL上云最佳选择

什么是云数据库POLARDB&#xff1f; POLARDB是阿里云自主研发的最新一代RDS关系型数据库&#xff0c;是特别针对互联网场景设计的Cloud-Native 云原生数据库。POLARDB for MySQL版本&#xff0c;在提供100%兼容MySQL5.6/8.0的关系型事务处理ACID特性之上&#xff0c;能够提供完…

如何让社区版IDEA变得好用

如何让社区版IDEA变得好用 背景 收费版的idea功能非常强大&#xff0c;但是收费&#xff1b;社区版的免费&#xff0c;但是功能被阉割了。如何才能让社区版Idea变得好用&#xff0c;一、打开项目前进行全局配置&#xff1b;二&#xff0c;寻求各种插件的支持。在经过全局配置…

迅睿CMS邮箱设置QQ邮箱为例

邮箱设置 1、服务器地址两个&#xff0c;普通与企业。 普通&#xff1a;ssl://smtp.qq.com企业&#xff1a;ssl://smtp.exmail.qq.com 2、端口号为&#xff1a;465 3、邮箱账号&#xff1a;填写自己的QQ邮箱作为发布服务器。 4、邮箱密码&#xff1a;到QQ邮箱账号中获取“…

Git学习篇

目录 使用命令导入项目 使用命令导入项目 1. 使用git init 命令初始化一个新的Git仓库。 git init 是 Git 命令&#xff0c;用于初始化一个新的 Git 仓库。当您想要开始跟踪一个新项目的版本控制时&#xff0c;可以运行 git init 命令来初始化一个空的 Git 仓库。 如果出现以下…

Windows电脑高颜值桌面便利贴,便签怎么设置

在这个看颜值的时代&#xff0c;我们不仅在衣着打扮上追求时尚与美观&#xff0c;就连电脑桌面也不愿放过。一张唯美的壁纸&#xff0c;几款别致的小工具&#xff0c;总能让我们的工作空间焕发出不一样的光彩。如果你也热衷于打造高颜值的电脑桌面&#xff0c;那么&#xff0c;…

用docker搭建的Vulfocus镜像管理界面没有镜像可以拉取解决办法

ps&#xff1a;截止到今天2023.4.2&#xff0c;kali和vps的docker拉取的vulfocus镜像会有版本的区别&#xff0c;虽然都是拉取的最新版&#xff0c;vps上镜像为3个月以前&#xff0c;kali上为16个月以前&#xff0c;所以在修改 views.py 文件时&#xff0c;可能会发现文件内容不…

国产化服务器开启NTP功能并向NTP时钟服务器同步

1.备份/etc/chrony.conf文件&#xff1b; cp -rp /etc/chrony.conf /etc/chrony.conf.bak.20240522 2.修改chrony.conf文件&#xff0c;增加NTP时钟信息。&#xff08;客户端填写时钟同步服务器的IP地址或者域名&#xff0c;我这里写的IP地址。下面Allow NTP Client是只允许…

易备数据备份软件: 快速备份 MySQL\SQL Server\Oracle\泛微 OA 数据库

易备数据备份软件支持对 SQL Server、Oracle、MySQL、PostgreSQL、MariaDB、泛微 OA 等数据库进行快速备份&#xff0c;备份过程不会对任何服务造成中断。 使用一份授权&#xff0c;可以备份无限量的数据库&#xff0c;不管数据库服务器是否在本机、本地网络、或是远程网络。可…

文心智能体平台 | 想象即现实

目录 文心智能体平台介绍平台简介通过平台能做什么平台的优势智能体介绍智能体类型AI 插件介绍 动手创建一个智能体访问平台并进行账号注册根据适合的方式选择智能体类型快速创建智能体智能体个性化模块配置 总结注意事项我的智能体 文心智能体平台介绍 平台简介 文心智能体平…

1、C++编程概述

文章目录 一、基本概念二、数据的表示及运算计算机中数据表示进制间相互转化二进制计算规则 三、计算机数据的存储单位四、机器数和码制五、机器数运算机器数的加减运算机器数的乘除运算 面向对象编程语言把事物看成是具有属性和行为的对象&#xff0c;然后通过抽象找出属于同一…

共筑信创新生态:DolphinDB 与移动云 BC-Linux 完成兼容互认

近日&#xff0c;DolphinDB 数据库软件 V2.0 与中国移动通信集团公司的移动云天元操作系统 BC-Linux 完成兼容性适配认证。经过双方共同严格测试&#xff0c;DolphinDB 性能及稳定性等各项指标表现优异&#xff0c;满足功能及兼容性测试要求。 此次 DolphinDB 成功通过移动云 B…

AWS 高防和阿里云高防深度对比

随着网络攻击的不断增加&#xff0c;企业对于网络安全的需求也越来越高。在这种情况下&#xff0c;高防护服务成为了企业网络安全的重要组成部分。AWS和阿里云作为全球领先的云计算服务提供商&#xff0c;都提供了高防护服务&#xff0c;但它们之间存在着一些差异。我们九河云一…