代码随想录刷题-数组-长度最小的子数组
文章目录
- 长度最小的子数组
- 习题
- 暴力解法
- 滑动窗口
长度最小的子数组
本节对应代码随想录中:代码随想录,讲解视频:拿下滑动窗口! | LeetCode 209 长度最小的子数组_哔哩哔哩_bilibili
习题
题目链接:209. 长度最小的子数组 - 力扣(LeetCode)
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
示例 1:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
暴力解法
直接能想到的就是用两个 for 循环,第一个循环遍历起始位置,第二个 for 循环向后遍历直到找到满足其和 ≥ target 的位置,我的代码如下(非最优,并且会超时,仅用于个人分析记录):
class Solution {public:int minSubArrayLen(int target, vector<int>& nums) {int res = 999999;for (int i = 0; i < nums.size(); i++) {int sum = 0, count = 999999;for (int j = i; j < nums.size(); j++) {sum += nums[j];if (sum >= target) {count = j - i + 1;break;}}if (count < res) {res = count;}}if(res!=999999){return res;}return 0;}
};
比较代码随想录上的暴力解法,有以下几点可以注意下
- 初始 res 时本意是想初始一个比较大的值,用
res=INT32_MAX更好INT_MAX一般和INT32_MAX相同,但如果是16位时,INT_MAX要更小点,所以用INT32_MAX更好
- 代码中后面两个 if 判断换成三元运算符更好,即 ` ? :
滑动窗口
C++中的滑动窗口是一种常见的数组/字符串问题的解决方案,它可以将一个问题的时间复杂度从 O(n^2)降低到 O(n)或者 O(nlogn),通常涉及到从给定的数据序列中找到需要进行操作的子串或子序列等。
滑动窗口的基本思路是:用两个指针表示现在关注的区间,即左端点(left pointer)和右端点(right pointer),让其构成一个窗口。移动右指针扩大长度,直到包含满足条件的子串(比如大于等于target)。然后,尝试缩小左端点以尽可能的减小满足条件的窗口长度,同时继续移动右指针,查找再次满足条件的子串。重复这个过程直到最右侧,得到最优解。
暴力解法中我们是遍历窗口的初始位置,对于每个初始位置向后遍历剩余元素寻找满足条件的窗口。而滑动窗口是遍历窗口的结束位置,如果当前窗口满足条件,那左边的指针就要向右移动即缩小窗口,其实也算是双指针。
class Solution {public:int minSubArrayLen(int target, vector<int>& nums) {int left = 0, sum = 0,subLength = 0;int ans = INT32_MAX; // 答案初始化为整数最大值for (int right = 0; right < nums.size(); right++) {sum += nums[right];while (sum >= target) { // 当sum>=target时,意味着当前窗口的总值大于等于target了subLength = (right - left + 1); // 取子序列的长度ans = ans < subLength ? ans : subLength; // 更新anssum -= nums[left]; // 窗口右移那就要减去原来窗口左边的值left++; // 通过左指针向右移动收缩窗口}}return ans == INT32_MAX ? 0 : ans; // 如果没找到就返回0}
};
代码中 while (sum >= target) 使用的是 while 而不是 if,因为当缩小窗口的时候是一个循环的过程。
如1 1 1 4中 target=4,那找到满足条件的窗口=4的时候,左指针应该是从初始的1不断向右移动直到新的窗口不大于等于 target 时停止
相关文章:
代码随想录刷题-数组-长度最小的子数组
文章目录长度最小的子数组习题暴力解法滑动窗口长度最小的子数组 本节对应代码随想录中:代码随想录,讲解视频:拿下滑动窗口! | LeetCode 209 长度最小的子数组_哔哩哔哩_bilibili 习题 题目链接:209. 长度最小的子数…...
成功解决安装MySQL5.7提示公钥GPG密钥配置为file:///etc/pki/rpm-gpg/RPM-GPG-KEY-mysql
前言 大家好,我是沐风晓月,今天做MySQL5.7安装的时候遇到问题了,我们一起来复盘下这个问题,如果你使用我的方法没有解决,一定要留言给我,我们一起来排查和学习和完善。 本文收录于csdn 我是沐风晓月的专栏 【日常遇到的疑难问题和bug解决】 ,若点击无法跳转,请在csdn …...
vue配置环境变量
目录 创建配置文件 .env.development 文件 .env.production 文件 .env.dev 文件 使用变量 配置 package.json 文件 例子:在 api.js 使用 可以继续添加 创建配置文件 在根目录与 package.json 同级创建文件 .env.development、 .env.production、.env.dev 文件…...
js学习3(数组)
目录 结构图 数组操作 每日一练 结构图 数组操作 ## 数组中可以存储任何类型元素 ## 创建: 字面量([...])、创建对象(new Array(arr_len)) ## 遍历: 循环遍历、forEach(callback)、map(callback)、filter(callback)、every(callback)、some(callback)、…...
不用写代码也能开发,产品经理是怎么做到的?
产品经理再也不用求开发了……就在前几天,我做的小程序上线了! 从产品原型设计,前端开发后端开发,产品部署到运维,都是由我1个人完成的。 我是啥时候学会写代码的呢?不瞒你说,我一行代码都没写…...
Android源码分析 - Parcel 与 Parcelable
0. 相关分享 Android-全面理解Binder原理 Android特别的数据结构(二)ArrayMap源码解析 1. 序列化 - Parcelable和Serializable的关系 如果我们需要传递一个Java对象,通常需要对其进行序列化,通过内核进行数据转发,…...
数字孪生与 UWB 技术创新融合:从单点测量到全局智能化
人员定位是指利用各种定位技术对人员在特定场所的位置进行准确定位的技术。人员定位技术主要应用于需要实时监控、管理和保障人员安全的场所,如大型厂区、仓库、医院、学校、商场等。人员定位技术的应用范围非常广泛,例如:-在工厂生产线上&am…...
蓝桥杯嵌入式PWM_IN(打开中断)
1.原理图 2.配置 3.代码 关键函数 HAL_TIM_IC_Start_IT(&htim3,TIM_CHANNEL_1) HAL_TIM_IC_CaptureCallback(TIM_HandTypeDef *htim)//回调函数 HAL_TIM_GET_COUNTER(&htim3) __HAL_TIM_SetCounter(&htim3,0)void HAL_TIM_IC_CaptureCallback(TIM_HandleTypeDef …...
蓝桥杯集训·每日一题Week1
前缀和(Monday) AcWing 3956. 截断数组(每日一题) 思路: 首先可以预处理出前缀和。判断数组长度如果小于 333 或者前 nnn 项不是 333 的倍数,则可以直接输出 000。 否则就枚举所有 s[i]s[n]3s[i] \cfrac…...
25k的Java开发常问的ThreadLocal问题有哪些?
前言:ThreadLocal问的比较多的是和Synchronized的区别、ThreadLocal被设计弱引用、存储元素的过程、实现线程隔离的原理。 文章目录 ThreadLocalThreadLocal定义ThreadLocal与Synchronized的区别ThreadLocal底层实现ThreadLocalMap存储元素的过程ThreadLocal实现线程隔离的原理…...
R语言基础(四):数据类型
R语言基础(一):注释、变量 R语言基础(二):常用函数 R语言基础(三):运算 5.数据类型 5.1 基本数据类型 R语言基本数据类型大致有六种: 整数Integer、浮点数Numeric、文本(字符串)Character、逻辑(布尔)Logical、复合类型Complex、…...
批处理命令--总结备忘「建议收藏」
批处理命令--总结备忘「建议收藏」 前言1、基础语法:2、批处理基本命令3、实例3.1 打开虚拟目录3.2 以当前时间为文件名,建文件夹3.3 备份postgresql数据库前言 最近用批处理命令做了一些postgresql数据库的备份,打开虚拟环境。。。发现批处理处理一些常用重复工作时真的很…...
面试知识点梳理及相关面试题(十一)-- docker
1. Docker和虚拟机的区别 容器不需要捆绑一整套操作系统,它只需要满足软件运行的最小内核就行了。 传统虚拟机技术是虚拟出一整套硬件后,在其上运行一个完成操作系统,在该系统上再运行所需应用进程容器内的应用进程直接运行于宿主的内核&am…...
k8s--services(微服务)
文章目录一、k8s网络通信service和iptables的关系二、services1.简介2.默认3.IPVS模式的service4.clusterip5.headless6.从外部访问service的三种方式(1)nodeport(2)loadbalancer7.metallb一、k8s网络通信 k8s通过CNI接口接入其他…...
【Java开发】设计模式 01:单例模式
1 单例模式介绍单例模式(Singleton Pattern)是Java中最为基础的设计模式。这种类型的设计模式属于创建型模式,它提供了一种创建对象的最佳方式。这种模式涉及到一个单一的类,该类负责创建自己的对象,同时确保只有单个对…...
10、go工程化与标准库
目录一、用go mod管理工程二、包引入规则三、init调用链四、可见性五、标准库1 - 时间函数2 - 数学计算3 - I/O操作4 - 编码一、用go mod管理工程 初始化项目:go mod init $module_name,$module_name和目录名可以不一样。上述命令会生成go.mod文件 mod…...
【Selenium自动化测试】鼠标与键盘操作
在 WebDriver 中,与鼠标操作相关的方法都封装在ActionChains 类中,与键盘操作相关的方法都封装在Keys类中。下面介绍下这两个类中的常用方法。 鼠标操作 ActionChains类鼠标操作常用方法: context_click():右击double_click()&…...
自定义javax.validation校验枚举类
枚举类单一情况 package com.archermind.cloud.phone.dto.portal.external.validation.validator;import com.archermind.cloud.phone.dto.portal.external.validation.constraints.EnumValidation; import lombok.extern.slf4j.Slf4j;import javax.validation.ConstraintVali…...
[Java·算法·中等]LeetCode39. 组合总和
每天一题,防止痴呆题目示例分析思路1题解1分析思路2题解2👉️ 力扣原文 题目 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ,找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ,并以列表形…...
【Linux】vi和vim编辑器
目录主题主题 三种常见模式: 正常模式 以vim 打开一个档案就直接进入一般模式了(这是默认的模式)。在这个模式中,你可以使用[上下左右]按键来移动光标,你可以使用『删除字符』或『删除整行』来处理档案内容,也可以使用「复制、…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
三维GIS开发cesium智慧地铁教程(5)Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点: 路径验证:确保相对路径.…...
学校招生小程序源码介绍
基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码,专为学校招生场景量身打造,功能实用且操作便捷。 从技术架构来看,ThinkPHP提供稳定可靠的后台服务,FastAdmin加速开发流程,UniApp则保障小程序在多端有良好的兼…...
Cinnamon修改面板小工具图标
Cinnamon开始菜单-CSDN博客 设置模块都是做好的,比GNOME简单得多! 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇
根据 QYResearch 发布的市场报告显示,全球市场规模预计在 2031 年达到 9848 万美元,2025 - 2031 年期间年复合增长率(CAGR)为 3.7%。在竞争格局上,市场集中度较高,2024 年全球前十强厂商占据约 74.0% 的市场…...
C++中vector类型的介绍和使用
文章目录 一、vector 类型的简介1.1 基本介绍1.2 常见用法示例1.3 常见成员函数简表 二、vector 数据的插入2.1 push_back() —— 在尾部插入一个元素2.2 emplace_back() —— 在尾部“就地”构造对象2.3 insert() —— 在任意位置插入一个或多个元素2.4 emplace() —— 在任意…...
