稀碎从零算法笔记Day6-LeetCode:长度最小的子数组

news/2024/4/24 13:58:18/文章来源:https://blog.csdn.net/m0_63356844/article/details/136424362

前言:做JD的网安笔试题,结果查找子串(单词)这个操作不会。痛定思痛,决定学习滑动数组

题型:数组、双指针、滑动窗口

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

来源:LeetCode 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度如果不存在符合条件的子数组,返回 0 。

题目样例

示例 1:

输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2:

输入:target = 4, nums = [1,4,4]
输出:1

示例 3:

输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0

提示:

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 105

题目思路

初见:用两个for循环,把字符串遍历一遍(相当于把父串中所有的子串的情况全列出来,然后看看string是否相等)。这样时间复杂度太高,而且练不到滑动窗口。

探索:本着用滑动窗口的目的,方法自然也锁定了下来。【滑动窗口】本质上还是【双指针】进行操作。题目中有【子串】、【最大串】、【最小串】等字眼时可以考虑使用【滑动窗口】。

主要思路就是①【right指针】后移,然后看【总和】时候满足题目条件(本题条件为:总和>=target)②如果满足条件,记录【当前窗口的长度】后,让【left】指针后移,再看看【窗口内元素】的和,是否依然满足条件..

C++代码

因为暴力没有实现,这里只贴滑动窗口的code。

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int left=0,len=nums.size(),answer=INT_MAX,sum=0;for(int right=0;right<len;right++){sum=sum+nums[right];// 条件:sum>=targetwhile(sum>=target){//让answer的值可以一直变answer=min(answer,right-left+1);sum-=nums[left];left++;}}//answer==len-1,说明answer的值没变过,说明right一直移动了,都没能sum>=targetreturn answer==INT_MAX? 0 : answer ;}
};

结算页面

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

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

相关文章

VS配置开发与远程调试笔记

先简单写一下&#xff0c;后续详细补充 场景&#xff1a;本地机器开发&#xff0c;虚拟机调试 准备工作&#xff1a; 由于要将生成的文件生成在虚拟机&#xff0c;避免反复拷贝&#xff0c;直接配置虚拟机共享文件夹进行写入&#xff0c;步骤如下&#xff1a; 虚拟机打开网…

修复通达OA 百度ueditor 文件上传漏动

前些日子&#xff0c;服务器阿里云监控报警&#xff0c;有文件木马文件&#xff0c;因为非常忙&#xff0c;就没及时处理&#xff0c;直接删除了木马文件了事。 谁知&#xff0c;这几天对方又上传了木马文件。好家伙&#xff0c;今天不花点时间修复下&#xff0c;你都传上瘾了…

hadoop学习中遇到的问题一

由于看视频总是断断续续&#xff0c;经常遇到各种报错&#xff0c;现将遇到的问题进行总结。 hadoop学习中遇到的问题&#xff1a;hadoop拒绝连接 hadoop安装好之后&#xff0c;在本地浏览器输入地址http://192.168.222.102:9870&#xff0c;提示拒绝连接。在网上找了很多相关…

【Unity开发】【VR】PICO项目在运行编辑器时无法正常显示游戏场景

【背景】 做了一个PICO项目&#xff0c;真机在手边时开发后用PC的Preview模式直接调试&#xff0c;真机不在手边时希望用VRTK的Simulation Rig&#xff0c;用键鼠模拟控制器输入进行快速调试。但是发现Simulation Rig状态下运行后&#xff0c;游戏场景变得很怪&#xff0c;很多…

44.网络编程/静态库动态库相关知识20240307

一、基于UDP的网络聊天室 项目需求&#xff1a; 如果有用户登录&#xff0c;其他用户可以收到这个人的登录信息如果有人发送信息&#xff0c;其他用户可以收到这个人的群聊信息如果有人下线&#xff0c;其他用户可以收到这个人的下线信息服务器可以发送系统信息。 服务器代码…

O2O:Sample Efficient Offline-to-Online Reinforcement Learning

IEEE TKDE 2024 paper Introduction O2O存在策略探索受限以及分布偏移问题&#xff0c;进而导致在线微调阶段样本效率低。文章提出OEMA算法首先使用离线数据训练乐观的探索策略&#xff0c;然后提出基于元学习的优化方法&#xff0c;减少分布偏移并提高O2O的适应过程。 Meth…

23种设计模式——工厂方法模式

定义&#xff1a; 一个用于创建对象的接口&#xff0c;让子类决定实例化哪一个类。工厂方法使一个类的实例化延迟到其他子类。 工厂方法通用类图&#xff1a; 这个图更好理解 在工厂方法模式中&#xff0c;抽象产品类Product负责定义产品的共性&#xff0c;实现对事物最抽象的…

LeetCode 刷题 [C++] 第3题.无重复字符的最长子串

题目描述 给定一个字符串 s &#xff0c;请你找出其中不含有重复字符的 最长子串 的长度。 题目分析 可以使用滑动窗口加哈希表来实现&#xff1a; 使用start和end两个变脸来表示滑动窗口的头部位置和尾部位置&#xff0c;两者开始均为0&#xff1b;借助哈希表来记录已经遍…

编译内核错误 multiple definition of `yylloc‘

编译内核错误 # make ARCHarm CROSS_COMPILEarm-mix410-linux- uImageHOSTLD scripts/dtc/dtc /usr/bin/ld: scripts/dtc/dtc-parser.tab.o:(.bss0x10): multiple definition of yylloc; scripts/dtc/dtc-lexer.lex.o:(.bss0x0): first defined here collect2: error: ld ret…

【蓝桥杯】路径之谜(DFS)

一.题目描述 小明冒充 X 星球的骑士&#xff0c;进入了一个奇怪的城堡。 城堡里边什么都没有&#xff0c;只有方形石头铺成的地面。 假设城堡地面是 nn 个方格。如下图所示。 按习俗&#xff0c;骑士要从西北角走到东南角。可以横向或纵向移动&#xff0c;但不能斜着走&#x…

Android使用WebView打开外部网页链接

发布Android应用&#xff0c;除了用原生开发外&#xff0c;更多是采用内嵌H5网页的方式来做&#xff0c;便于更新以及多平台使用。 一、第一种方式是直接通过WebView打开外部H5链接。 新建Android工程 直接创建一个工程&#xff0c;点击运行就可以了&#xff0c;打开是个空页…

Cloud-Nacos服务治理-Feign服务调用

构建Cloud 父工程依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apache.…

redis实现分布式全局唯一id

目录 一、前言二、如何通过Redis设计一个分布式全局唯一ID生成工具2.1 使用 Redis 计数器实现2.2 使用 Redis Hash结构实现 三、通过代码实现分布式全局唯一ID工具3.1 导入依赖配置3.2 配置yml文件3.3 序列化配置3.4 编写获取工具3.5 测试获取工具 四、运行结果 一、前言 在很…

蓝桥杯练习题——归并排序

1.火柴排队 思路 1.求最小值的时候&#xff0c;可以直接按升序排序&#xff0c;这样得到的值就是最小值 2.求最小交换次数的时候&#xff0c;不能直接排序&#xff0c;因为只能交换相邻的数&#xff0c;只需要知道他们的相对大小&#xff0c;所以可以先用离散化&#xff0c;把…

百度地图城市点位数据下载并转换

概述 在浏览百度地图开放平台的时候&#xff0c;发现有个资源下载页面&#xff0c;里面有个城市中心点位和百度地图行政区划adcode映射表数据&#xff0c;这是一个经常使用到的数据&#xff0c;本文实现将这个数据转换为geojson&#xff0c;并借助QGIS转换为经纬度坐标或火星坐…

IDEA自带 .http 请求工具文档

基础语法 请求格式 基础格式 Method Request-URI HTTP-Version Header-field: Header-valueRequest-Body其中&#xff0c;GET 请求可以省略 Method 不写&#xff1b;HTTP-Version 可以省略不写&#xff0c;默认使用 1.1 版本。 示例&#xff1a; GET https://www.baidu.co…

【Spring云原生系列】Spring RabbitMQ:异步处理机制的基础--消息队列 原理讲解+使用教程

&#x1f389;&#x1f389;欢迎光临&#xff0c;终于等到你啦&#x1f389;&#x1f389; &#x1f3c5;我是苏泽&#xff0c;一位对技术充满热情的探索者和分享者。&#x1f680;&#x1f680; &#x1f31f;持续更新的专栏《Spring 狂野之旅&#xff1a;从入门到入魔》 &a…

docker的网络配置

文章目录 1、网络模式1.1、bridge模式(默认模式)1.2、host模式 2、bridge模式3、自定义网络 1、网络模式 Docker在创建容器时有四种网络模式&#xff1a;bridge/host/container/none&#xff0c;bridge为默认不需要用–net去指定&#xff0c;其他三种模式需要在创建容器时使用…

创邻科技获评环紫金港创新生态圈智源创新企业

3月1日&#xff0c;由杭州城西科创大走廊管理委员会指导&#xff0c;中共杭州市西湖区委员会、西湖区人民政府主办的“环紫金港创新生态圈”行动推进大会暨2024年紫金港科技城经济高质量发展大会在杭州举办。凭借重要的生态位置和创新业务成果&#xff0c;创邻科技受邀参会并被…

读《文明之光》第1册总结

人类几千年的文明史和地球的历史相比&#xff0c;实在是太短暂了&#xff0c;大约相当于几分钟和一年的关系。人类已经走过的路&#xff0c;相比今后要走的漫漫长路&#xff0c;只能算是刚刚起步。如果跳出一个个具体事件&#xff0c;站在历史的高度去看&#xff0c;我们会发现…