【C++】滑动窗口:长度最小的子数组

1.题目

2.算法分析

这种题目,首先想到的是暴力穷举法:

用两层循环取遍该数组的所有子数组,然后找到那个最短的就可以了。

我们的滑动窗口就是对这种暴力穷举法进行优化:

主要是舍弃的思想,舍弃那些一定不可能是最终答案的结果:

如果该数组的某个子数组已经符合题意了,那么包含这个子数组的所有数组都不可能是最短的数组,统统舍掉!

举个例子:

ret[]={5,2,3,4,6};target=7;

子数组{5,2}是符合题意的,那么包含该子数组的数组例如{5,2,3},{5,2,3,4}等等不可能是最短的。

这时我们就需要从5的下一个位置开始考虑。

2.1什么是滑动窗口

那么我们来介绍一下什么是滑动窗口:

滑动窗口其实就是同向的双指针算法,利用题目的单调性来进行优化暴力穷举法。

由于同向的两个指针遍历数组的动作很像窗口两端的滑动,所以称这种算法为滑动窗口。

如何使用滑动窗口呢?

进窗口->判断->出窗口->更新结果。(更新结果的位置不固定)。

时间复杂度:

大概遍历两次数组,所以时间复杂度为O(n)。

3.提交结果与代码实现

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n=nums.size(),len=INT_MAX,sum=0;for(int left=-1,right=0;right<n;right++){sum+=nums[right];//进窗口while(sum>=target){//判断len=min(len,right-left);//更新结果sum-=nums[++left];//出窗口}}return len==INT_MAX?0:len;}
};

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

jupyter notebook切换conda虚拟环境

首先&#xff0c;切换到某个虚拟环境&#xff0c;本人切换到了d2l环境&#xff1a; (d2l) C:\Users\10129>pip install ipykernel然后&#xff0c;如代码所示安装ipykernel包 最后&#xff0c;按下述代码执行&#xff1a; (d2l) C:\Users\10129>python -m ipykernel i…

857.雇佣K名工人的最低成本

题目说的其实是有点乱的,所以我们可能抓不住重点,甚至都不太清楚规则,比如 eg. quality[3,1,10,10,1] wage[4,8,200,200,7] 这里是选下标0,1,4 ->单价为8 但是想清楚其实就很easy. 就是 贪心(sort) 优先队列 梳理下我们发现其实要让每个人得到最低期望,就要按照当前最贵…

vue中配置 测试、准生产、生产环境

在package.json,scripts中配置 "dev": "vue-cli-service serve --open --mode dev",在项目根目录下配置 新建 .env.dev 和.env.development文件 //类似于title NODE_ENV "serve" //各环境API数据接口请求地址 VUE_APP_BASE_API "http:…

Python绘制的好看统计图

代码 sx [Accent, Accent_r, Blues, Blues_r, BrBG, BrBG_r, BuGn, BuGn_r, BuPu, BuPu_r, CMRmap, CMRmap_r, Dark2, Dark2_r, GnBu, GnBu_r, Greens, Greens_r, Greys, Greys_r, OrRd, OrRd_r, Oranges, Oranges_r, PRGn, PRGn_r, Paired, Paired_r, Pastel1, Pastel1_r, P…

DataTrove:一款针对大规模文本数据的处理、过滤和消除重复数据工具

关于DataTrove DataTrove是一款针对大规模文本数据的处理、过滤和消除重复数据工具&#xff0c;该工具可以通过提供一组平台无关的可定制管道处理块&#xff0c;帮助广大研究人员从各种复杂脚本中解放出来&#xff0c;同时还允许我们轻松添加自定义功能。 DataTrove所实现的数…

Linux内核之原子操作:atomic_long_inc用法实例(六十六)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…

【C语言】atoi和atof函数的使用

人生应该树立目标&#xff0c;否则你的精力会白白浪费。&#x1f493;&#x1f493;&#x1f493; 目录 •&#x1f319;知识回顾 &#x1f34b;知识点一&#xff1a;atoi函数的使用和实现 • &#x1f330;1.函数介绍 • &#x1f330;2.代码演示 • &#x1f330;3.atoi函数的…

springboot + slf4j + log4j2

<!--Web依赖--> <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web</artifactId><exclusions><exclusion><groupId>org.springframework.boot</groupId><artifact…

Oracle 执行计划

1.执行计划 执行计划是一条查询语句在Oracle中的执行过程或访问路径的描述。 执行计划描述了SQL引擎为执行SQL语句进行的操作&#xff1b;分析SQL语句相关的性能问题或仅仅质疑查询优化器的决定时&#xff0c;必须知道执行计划&#xff1b;所以执行计划常用于sql调优。 2.查…

python学习笔记----异常、模块与包(九)

一、异常 1.1 什么是异常 在Python中&#xff0c;异常是程序执行时发生的错误。当Python检测到一个错误时&#xff0c;它会引发一个异常&#xff0c;这可能是由于多种原因&#xff0c;如尝试除以零、访问不存在的文件&#xff0c;或者尝试从列表中获取不存在的索引等。异常处…

在Centos7上部署LDAP服务

安装ldap和设置自起 - 安装ldap yum install -y openldap-servers openldap-clients openldap openldap-devel compat-openldap openldap-servers-sql- 启动和开机自起 systemctl start slapd systemctl enable slapd- 查看服务是否安装成功 配置ldap - 创建第一个管理账号…

基于MSOGI的交叉对消谐波信号提取网络MATLAB仿真

微❤关注“电气仔推送”获得资料&#xff08;专享优惠&#xff09; 模型简介&#xff1a; 此模型利用二阶广义积分器&#xff08;SOGI&#xff09;对基波电流和相应次的谐波电流进行取 &#xff0c;具体是通过多个基于二阶广义积分器的正交信号发生器 &#xff08; S&#xf…

JAVA面试之MQ

如何保证消息的可靠传输&#xff1f;如果消息丢了怎么办 数据的丢失问题&#xff0c;可能出现在生产者、MQ、消费者中。 &#xff08;1&#xff09;生产者发送消息时丢失&#xff1a; ①生产者发送消息时连接MQ失败 ②生产者发送消息到达MQ后未找到Exchange(交换机) ③生产者发…

按照数组原来的规律将新插入的数组插入(C语言)

一、N-S流程图&#xff1b; 二、运行结果&#xff1b; 三、源代码&#xff1b; # define _CRT_SECURE_NO_WARNINGS # include <stdio.h>int main() {//初始化变量值&#xff1b;int i 0;int j 0;int temp1 0;int temp2 0;int end 0;int number 0;int a[11] { 1, …

LeetCode 131 —— 分割回文串

阅读目录 1. 题目2. 解题思路3. 代码实现 1. 题目 2. 解题思路 首先&#xff0c;按照 LeetCode 5——最长回文子串 中的思路&#xff0c;我们先求出 d p dp dp&#xff0c;这样我们就知道了所有的子串是否是回文子串。 然后&#xff0c;我们进行一个 dfs 搜索&#xff0c;起…

Ubuntu系统安装nvfortran详细步骤【笔记】

实践设备&#xff1a;华硕FX-PRO&#xff08;NVIDIA GeForce GTX 960M&#xff09; Ubuntu系统安装NVFORTRAN&#xff08;NVIDIA Fortran Compiler&#xff09;步骤如下&#xff1a; 安装依赖项&#xff1a;在安装NVFORTRAN之前&#xff0c;你需要确保系统已经安装了一些必要…

使用docker安装redis

使用docker安装redis ①拉取镜像 docker pull redis:6.2.6② 创建容器 docker run -d --name forum-redis --restartalways -p 6379:6379 redis:6.2.6 redis-server --requirepass "dong97"③链接测试 打开Redis Desktop Manager&#xff0c;输入host、port、pas…

无法定位程序输入点QTextStream

当您的应用在调试模式下运行正常&#xff0c;但在发布&#xff08;发布构建&#xff09;后出现错误时&#xff0c;可能涉及到以下几个常见的原因&#xff1a; 动态链接库问题&#xff1a;发布构建可能没有包含必要的动态链接库&#xff08;DLL&#xff09;&#xff0c;或者没有…

《与 Apollo 共创生态——Apollo7周年大会干货分享》

&#x1f308;个人主页: Aileen_0v0 &#x1f525;热门专栏: 华为鸿蒙系统学习|计算机网络|数据结构与算法 ​&#x1f4ab;个人格言:“没有罗马,那就自己创造罗马~” 文章目录 阿波罗X企业自动驾驶解决方案自动驾驶技术提升与挑战自动驾驶系统功能与性能的详细解析<td alig…

Linux进程——进程的创建(fork的原理)

前言&#xff1a;在上一篇文章中&#xff0c;我们已经会使用getpid/getppid函数来查看pid和ppid,本篇文章会介绍第二种查看进程的方法&#xff0c;以及如何创建子进程&#xff01; 本篇主要内容&#xff1a; 查看进程的第二种方法创建子进程系统调用函数fork 在开始前&#xff…