209. 长度最小的子数组
209. 长度最小的子数组
力扣题目链接(opens new window)
给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。
示例:
输入:s = 7, nums = [2,3,1,2,4,3] 输出:2 解释:子数组 [4,3] 是该条件下的长度最小的子数组。
提示:
- 1 <= target <= 10^9
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^5
思路
滑动窗口
滑动窗口:不断的调整子序列的起始位置和终止位置,从而得到想要的结果。
在暴力解法中,是一个for循环滑动窗口的起始位置,一个for循环为滑动窗口的终止位置,用两个for循环完成了一个不断搜索区间的过程。
那么滑动窗口如何用一个for循环来完成这个操作呢?
只用一个for循环,那么这个循环的索引,一定是表示 滑动窗口的终止位置。
在本题中实现滑动窗口,主要确定如下三点:
- 窗口内是什么?
窗口就是满足其和 ≥ s 的长度最小的连续子数组。 - 如何移动窗口的起始位置?
窗口的起始位置如何移动:如果当前窗口的值大于s了,窗口就要向前移动了(也就是该缩小了)。 - 如何移动窗口的结束位置?
窗口的结束位置如何移动:窗口的结束位置就是遍历数组的指针,也就是for循环里的索引。
解题的关键在于 窗口的起始位置如何移动,如图所示:

可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况,不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。
class Solution {//方法:滑动窗口public int minSubArrayLen(int target, int[] nums) {int left = 0;//滑动窗口起始位置int sum = 0; //滑动窗口数值之和//结果取整型类型的最大值,便于和遍历的结果比较 int result = Integer.MAX_VALUE;for(int right = 0; right < nums.length; right++){sum += nums[right]; //使用while,每次更新 i(起始位置),并不断比较子序列是否符合条件while(sum >= target){//right - left + 1为子序列(滑动窗口)的长度result = Math.min(result, right - left + 1); sum -= nums[left++]; // 这里体现出滑动窗口的精髓之处,不断变更i(子序列的起始位置)}}// 如果result没有被赋值的话,就返回0,说明没有符合条件的子序列return result == Integer.MAX_VALUE ? 0 : result;}
}
- 时间复杂度:O(n)
- 空间复杂度:O(1)
相关文章:

209. 长度最小的子数组
209. 长度最小的子数组 力扣题目链接(opens new window) 给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。 示例: 输入…...

【数据结构与算法】查找(Search)【详解】
文章目录查找查找概论一、查找的基本概念顺序表查找一、定义二、算法有序表查找一、折半查找二、插值查找三、斐波那契查找线性索引查找一、稠密索引二、分块索引三、倒排索引二叉树排序与平衡二叉树一、二叉排序树1、定义2、二叉排序树的常见操作3、性能分析二、平衡二叉树1、…...

一文学会 Spring MVC 表单标签
✅作者简介:2022年博客新星 第八。热爱国学的Java后端开发者,修心和技术同步精进。 🍎个人主页:Java Fans的博客 🍊个人信条:不迁怒,不贰过。小知识,大智慧。 💞当前专栏…...

如何在 Windows10 下运行 Tensorflow 的目标检测?
前言 看过很多博主通过 Object Detection 实现了一些皮卡丘捕捉,二维码检测等诸多特定项的目标检测。而我跟着他们的案例来运行的时候,不是 Tensorflow 版本冲突,就是缺少什么包,还有是运行官方 object_detection_tutorial 不展示…...

【jvm系列-04】精通运行时数据区共享区域---堆
JVM系列整体栏目 内容链接地址【一】初识虚拟机与java虚拟机https://blog.csdn.net/zhenghuishengq/article/details/129544460【二】jvm的类加载子系统以及jclasslib的基本使用https://blog.csdn.net/zhenghuishengq/article/details/129610963【三】运行时私有区域之虚拟机栈…...
ctfshow愚人杯 re easy_pyc wp
一、反编译题目pyc文件 题目下载解压后是一个.pyc文件,那就去反编译看看呗,因为之前用过uncompyle6,直接去命令行执行 uncompyle6 -o ez_re.py ez_re.pyc 得到ez_re.py源码一份~ 但是这里我用uncompyle6反编译的结果不知道为啥就出来很多奇…...
Ubuntu18.04 系统中本地代码上传至Gitlab库
主要步骤如下: 设置SSH Key 上传项目 1.创建SSH Key 每次上传可重新设置一个SSH Key或者使用已有SSH Key (1)创建SSH Key 创建一个新的SSH Key,终端输入以下指令,其中 “xxxxxx163.com” 是邮箱账号: s…...
Leetcode.1665 完成所有任务的最少初始能量
题目链接 Leetcode.1665 完成所有任务的最少初始能量 Rating : 1901 题目描述 给你一个任务数组 tasks,其中 tasks[i] [actuali, minimumi]: actuali是完成第 i 个任务 需要耗费 的实际能量。minimumi是开始第 i 个任务前需要达到的最低能…...

【C++笔试强训】第一天
选择题 解析:在for循环的循环条件(y 123) && (x < 4)中 ,&& 表示逻辑与,从左向右判断两边条件是否成立,只有当两边的条件都为真时,这条语句才为真。左边y 123是赋值语句,一直为真&…...

【网络安全软件】上海道宁与Cybereason为您提供未雨绸缪的攻击保护,终结对端点、整个企业以及网络上任何角落的网络攻击
Cybereason可收集 计算机网络内任何活动方面的数据 如运行当中的程序 被用户访问的文件以及 员工及任何获授权使用网络中的计算机人的 键盘输入和鼠标移动情况 Cybereason提供 即时结束网络攻击的精确度 在计算机、移动设备、服务器和云中 到战斗移动的任何地方 一、开…...
基于RK3568的Android11 适配 MIPI 屏幕
文章目录 前言一、mipi接口是什么?二、原理图三、屏幕点亮流程四、屏幕关键参数1.General Specification2. Power on/off sequence3.Timing五、屏幕初始化序列改写如何把原厂给的数据转换为设备需要的时序dcs小知识:初始化时序:退出时序:总结前言 在本小节会学习到如何适配…...
Ubuntu安装python
CentOS 安装 Python3 没什么坑,按照步骤一步步来就可以了。 但 Ubuntu 安装 Python3 的坑却不少,这里总结一下,避免以后继续踩坑。 我用的是 ubuntu16.04,安装最新版本的 Python3.8.3 第1步:安装编译环境 安装之前…...
django 运用pycharm的各种故障汇总(1)
一.用django入门第一个问题:pycharm的[community]社区版-免费开源与[professional]专业版注册收费两个版本:用django只能有[professional]版本便捷、专业; 解决方案的各种学习总结: 1.破解版:网上找了很多资料,基本已经没效果,不要报太大希望; 2.找中间途径然后有:Python 、…...

【设计模式】单例模式Singleton(Java)
文章目录定义类图Java经典实现懒汉Lazy Mode:饿汉Eager Mode:在饿汉下的多线程案例在懒汉下的多线程案例总结定义 单例模式(单件模式)确保一个类只有一个实例,并提供一个全局访问点。——HeadFirst 单例模式通过过防…...

机器学习中的公平性
文章目录机器学习公平性评估指标群体公平性指标个人公平性指标引起机器学习模型不公平的潜在因素提升机器学习模型公平性的措施机器学习公平性 定义: 机器学习公平性主要研究如何通过解决或缓解“不公平”来增加模型的公平性,以及如何确保模型的输出结果…...

Docker镜像之Docker Compose讲解
文章目录1 docker-compose1.1 compose编排工具简介1.2 安装docker-compose1.3 编排启动镜像1.4 haproxy代理后端docker容器1.5 安装socat 直接操作socket控制haproxy1.6 compose中yml 配置指令参考1.6.1 简单命令1.6.2 build1.6.3 depends_on1.6.4 deploy1.6.5 logging1.6.6 ne…...

蓝桥杯30天真题冲刺|题解报告|第三十天
大家好,我是snippet,今天是我们这次蓝桥省赛前一起刷题的最后一天了,今天打了一场力扣周赛,前面3个题都是有思路的,第三个题只过了一半的案例,后面看完大佬们的题解彻悟,下面是我今天的题解 目录…...
配置 Git Husky 代码提交约束
介绍 Git Husky 是一个可以管理 Git Hooks 的工具,它可以帮助我们在代码提交的时候运行脚本,以确保代码提交符合特定的规范和约定。 在 Git 中,允许在操作特定的事件时执行特定的脚本,这些事件我们称之为 Hooks。 Git Husky 利…...

IntelliJ IDEA 2023.1 最新变化
文章目录IntelliJ IDEA 2023.1 最新变化一. 主要更新1. 新 UI 增强 测试版启用新 UI2. 在项目打开时更早提供 IDE 功能3. 更快地导入 Maven 项目4.后台提交检查5. Spring Security 匹配器和请求映射的导航 Ultimate二. 用户体验1. 全 IDE 缩放2. 保存多个工具窗口布局的选项3. …...

stm32学习笔记-9 USART串口
9 USART串口 文章目录9 USART串口9.1 串口通信协议9.2 stm32的片上外设-USART9.3 USART收发相关实验9.3.1 实验1:串口发送9.3.2 实验2:移植printf函数9.3.3 实验3:串口发送接收9.4 USART串口数据包9.5 USART数据包相关实验9.5.1 实验1&#x…...
RestClient
什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端,它允许HTTP与Elasticsearch 集群通信,而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级ÿ…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...

智慧医疗能源事业线深度画像分析(上)
引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法
深入浅出:JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中,随机数的生成看似简单,却隐藏着许多玄机。无论是生成密码、加密密钥,还是创建安全令牌,随机数的质量直接关系到系统的安全性。Jav…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...

el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

Maven 概述、安装、配置、仓库、私服详解
目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...
使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度
文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...