【C++算法】10.滑动窗口_长度最小的子数组

文章目录

    • 题目链接:
    • 题目描述:
    • 解法
    • C++ 算法代码:
    • 图解


题目链接:

209. 长度最小的子数组


题目描述:

1170422f911c06f1e598ea59a29ecac5


解法

解法一:暴力求解(会超时)

暴力枚举出所有子数组的和。

查找子数组n2,求和n

一共O(n3)

优化:

求和的时候,可以把上次求和的结果存起来,往后加一位的时候直接把那一位的值加到上次的和里面。

解法二:滑动窗口O(n)

利用单调性,使用同向双指针来优化。(同向双指针也叫滑动窗口)

  1. left=0,right=0,标记窗口的左右端点
  2. 进窗口
  3. 判断,更新结果🌟,出窗口

2-3步是一直循环的

例如:nums=[2,3,1,2,4,3]

bf6f7a41e4c0f24e3385c0f646767131

移动到sum>=target

6534792b2aa1723748d3fa03cddf0bc9

然后left右移,因为如果left不动,right继续往后得到的都不是长度最小的数组了。

aa3c1e36590f6a910fb325c20970fa2b

sum<target,right右移

98dad4dddeee070163985dcba31f6609

依次类推

然后窗口的长度可以用len来记录,每次判断后先更新结果,然后出窗口。


C++ 算法代码:

解法一:暴力求解(会超时)

class Solution {public:int minSubArrayLen(int target, vector<int>& nums) {// 记录结果int ret = INT_MAX;int n = nums.size();// 枚举出所有满足和大于等于 target 的子数组[start, end// 由于是取到最小,因此枚举的过程中要尽量让数组的长度最小// 枚举开始位置for (int start = 0; start < n; start++){int sum = 0; // 记录从这个位置开始的连续数组的和// 寻找结束位置for (int end = start; end < n; end++){sum += nums[end]; // 将当前位置加上if (sum >= target) // 当这段区间内的和满足条件时{// 更新结果,start 开头的最短区间已经找到ret = min(ret, end - start + 1);break;}}}// 返回最后结果return ret == INT_MAX ? 0 : ret;}
};

解法二:

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); // 更新结果sum -= nums[left++]; // 出窗口}}return len == INT_MAX ? 0 : len;}
};

图解

nums=[2,3,1,2,4,3]

target=7

  1. n=6,sum=0,right=0,left=0,target=7,len=INT_MAX(确保min使用的时候不会把len的初始值当作最小值)

b000e57b75676632dd08955353dcf5f6

  1. sum=2

    sum<target,right++

a26691d21d504806c3bd541f0e84a510

  1. sum=5

    sum<target,right++

88c4dd7832bfdeb9cbaf7889c41dbef0

  1. sum=5

    sum<target,right++

216734ef9302afa8c1e63071380c329f

  1. sum=8

    sum>target,len=4

    sum=sum-nums[left++]=8-2=6

ed97423f50bce4cfa4726e06b66751e7

  1. sum=6

    sum<target,right++

d055ae3daef5ce1fefa302efca207622

  1. sum=10

    sum>target,len=4

    sum=sum-nums[left++]=10-3=7

d80a4ad69c27c089f1261afef6455762

  1. sum=7

    sum=target,len=3

    sum=sum-nums[left++]=7-1=6

973a3fe82a527723d2848853fb0f99cb

  1. sum=6

    sum<target,right++

5b759f03d0c01c3cc4abdd5a1c2a8892

  1. sum=9

    sum>target,len=3

    sum=sum-nums[left++]=9-2=7

328afb03c2ae215109c04c4becc5ddbe

  1. sum=7

    sum=target,len=2

    sum=sum-nums[left++]=7-4=3

bd5301b2ad254ec8435695ecc4437004

  1. sum=3

    sum<target,right++

cc49d00b9fff8a978d8ef4972098214c

  1. 跳出for循环,return len == INT_MAX ? 0 : len;,这里返回2

  2. 程序结束

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

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

相关文章

云计算 Cloud Computing

文章目录 1、云计算2、背景3、云计算的特点4、云计算的类型&#xff1a;按提供的服务划分5、云计算的类型&#xff1a;按部署的形式划分 1、云计算 定义&#xff1a; 云计算是一种按使用量付费的模式&#xff0c;这种模式提供可用的、便捷的、按需的网络访问&#xff0c;进入可…

idea插件开发的第六天-开发一个笔记插件

介绍 Demo说明 本文基于maven项目开发,idea版本为2022.3以上,jdk为1.8本文在JTools插件之上进行开发本插件目标是做一款笔记插件,用于开发者在开发过程中随时记录信息仓库地址: jtools-notes JTools插件说明 Tools插件是一个Idea插件,此插件提供统一Spi规范,极大的降低了id…

微型导轨在IC制造设备的应用与优势

微型导轨的精度和稳定性对于机器的准确执行任务至关重要&#xff0c;其精确度通常用微米或毫米来衡量。其尺寸可以做到非常小&#xff0c;常运用在小型设备上&#xff0c;尤其是在IC制造设备中&#xff0c;其应用非常广泛。 在IC制造设备中主要用于半导体芯片的切割、封装和测试…

V2M2引擎源码BlueCodePXL源码完整版

V2M2引擎源码BlueCodePXL源码完整版 链接: https://pan.baidu.com/s/1ifcTHAxcbD2CyY7gDWRVzQ?pwdmt4g 提取码: mt4g 参考资料&#xff1a;BlueCodePXL源码完整版_1234FCOM专注游戏工具及源码例子分享

网站可疑问题

目标站点 Google hack 页面访问 抓包 POST /admin.php?actionlogin HTTP/2 Host: www.xjy.edu.cn Cookie: xkm_sidA6x4Cgw2zx User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:130.0) Gecko/20100101 Firefox/130.0 Accept: text/html,application/xhtmlxml,appl…

使用 Light Chaser 进行大屏数据可视化

引言 在当今数据驱动的世界中&#xff0c;数据可视化变得越来越重要。Light Chaser 是一款基于 React 技术栈的大屏数据可视化设计工具&#xff0c;通过简单的拖拽操作&#xff0c;你可以快速生成漂亮、美观的数据可视化大屏和看板。本文将介绍如何使用 Light Chaser 进行数据…

Redis:string类型

Redis&#xff1a;string类型 string命令设置与读取SETGETMSETMGET 数字操作INCRINCRBYDECRDECRBYINCRBYFLOAT 字符串操作APPENDSTRLENGETRANGESETRANGE 内部编码intembstrraw 在Redis中&#xff0c;字符串string存储的是二进制&#xff0c;以byte为单位&#xff0c;输入的二进…

【HTML+CSS】留言板plus实现全过程

创建一个具有动态留言的简约风格留言板 在本教程中&#xff0c;我们将学习如何创建一个简约风格的留言板&#xff0c;它具备动态留言显示和一些基本动画效果。这个留言板将使用HTML和CSS构建&#xff0c;最终实现一个既美观又实用的界面。 准备工作 首先&#xff0c;确保你的…

面试速通宝典——7

150. 数据库连接池的作用 数据库连接池的作用包括以下几个方面&#xff1a; 资源重用&#xff1a;连接池允许多个客户端共享有限的数据库连接&#xff0c;减少频繁创建和销毁连接的开销&#xff0c;从而提高资源的利用率。 统一的连接管理&#xff1a;连接池集中管理数据库连…

Stream流的终结方法(一)

1.Stream流的终结方法 2.forEach 对于forEach方法&#xff0c;用来遍历stream流中的所有数据 package com.njau.d10_my_stream;import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.function.Consumer; import java.util…

Swagger配置且添加小锁(asp.net)(笔记)

此博客是基于 asp.net core web api(.net core3.1)框架进行操作的。 一、安装Swagger包 在 NuGet程序包管理中安装下面的两个包&#xff1a; swagger包&#xff1a;Swashbuckle.AspNetCore swagger包过滤器&#xff1a;Swashbuckle.AspNetCore.Filters 二、swagger注册 在…

戴尔PowerEdge R840服务器亮黄灯 不开机

最近接修到一台东莞用户的DELL PowerEdge R840 服务器因为意外断电后&#xff0c;无法正常开机的问题&#xff0c; 大概故障现象是 插上电源线 按卡机按钮无响应&#xff0c;无法开机&#xff0c;无显示输出&#xff0c;工程师到现场检修&#xff0c;经过idrac中日志分析&#…

K8S真正删除pod

假设k8s的某个命名空间如&#xff08;default&#xff09;有一个运行nginx 的pod&#xff0c;而这个pod是以kubectl run pod命令运行的 1.错误示范&#xff1a; kubectl delete pod nginx-2756690723-hllbp 结果显示这个pod 是删除了&#xff0c;但k8s很快自动创建新的pod,但是…

C(九)while循环 --- 军训匕首操情景

匕首操&#xff0c;oi~oi~oi~~~~~ 接下来的几篇推文&#xff0c;杰哥记录的是三大循环结构的运行流程及其变式。 本篇的主角是while循环。&#x1f449; 目录&#xff1a; while循环 的组成、运行流程及其变式关键字break 和 continue 在while 循环中的作用while 循环的嵌套题目…

基于SSM的坚果金融投资管理系统、坚果金融投资管理平台的设计与开发、智慧金融投资管理系统的设计与实现、坚果金融投资管理系统的设计与应用研究(源码+定制+开发)

博主介绍&#xff1a; ✌我是阿龙&#xff0c;一名专注于Java技术领域的程序员&#xff0c;全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师&#xff0c;我在计算机毕业设计开发方面积累了丰富的经验。同时&#xff0c;我也是掘金、华为云、阿里云、InfoQ等平台…

我为什么决定关闭ChatGPT的记忆功能?

你好&#xff0c;我是三桥君 几个月前&#xff0c;ChatGPT宣布即将推出一项名为“记忆功能”的新特性&#xff0c;英文名叫memory。 这个功能听起来相当吸引人&#xff0c;宣传口号是让GPT更加了解用户&#xff0c;仿佛是要为我们每个人量身打造一个专属的AI助手。 在记忆功…

vue结合element-ui实现列表拖拽变化位置,点击拖动图标拖动整个列表元素,使用tsx格式编写

先来看下需要实现的效果 当鼠标放在左侧图标上时&#xff0c;可以拖动整个列表元素&#xff0c;调整顺序 思路介绍 使用draggable可以设置元素可拖动&#xff0c;然后分别设置三个事件处理函数&#xff0c;监听onDragstart、onDragover、onDragend三个事件 注意&#xff1a…

青少年科普教学系统小程序的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;管理员管理&#xff0c;基础数据管理&#xff0c;作品信息管理&#xff0c;通知公告管理&#xff0c;视频信息管理&#xff0c;系统管理 微信端账号功能包括&#xff1a;系统首页&#xff0c;视频信息&…

html+css+js实现Collapse 折叠面板

实现效果&#xff1a; HTML部分 <div class"collapse"><ul><li><div class"header"><h4>一致性 Consistency</h4><span class"iconfont icon-jiantou"></span></div><div class"…

【unity进阶知识6】Resources的使用,如何封装一个Resources资源管理器

文章目录 一、Unity资源加载的几种方式1、Inspector窗口拖拽2、Resources3、AssetBundle4、Addressables&#xff08;可寻址资源系统&#xff09;5、AssetDatabase 二、准备三、同步加载Resources资源1、Resources.Load同步加载单个资源1.1、基本加载1.2、加载指定类型的资源1.…