长度最小的子数组(Java详解)
目录
题目描述
题解
思路分析
暴力枚举代码
滑动窗口代码
题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
示例:
输入:target = 7, nums = [2,3,1,2,4,3] 输出:2
输入:target = 4, nums = [1,4,4] 输出:1
题解
思路分析
题目要求我们找到和 >= target 的 最小 且 连续 的子数组,我们很容易想到暴力枚举的方法,即访问数组的每一个元素i,并将i作为第一个元素,向后寻找

暴力枚举代码
class Solution {public int minSubArrayLen(int target, int[] nums) {int count = 0;for(int i = 0; i < nums.length; i++){int sum = 0;//向后遍历找到以nums[i]为起始元素的最小数组for(int j = i; j < nums.length;j++){sum += nums[j];if(sum >= target){//更新目标值 由于count的初始值为0,因此需要更新初始值,//否则最小值恒为0if(count > j-i+1 || count == 0){count = j-i+1;}break;}}}//若count未被更新,则返回0,即没有子数组的和大于target,//若count被跟新,则返回最小的子数组长度return count;}
}
此时我们通过遍历访问了数组的每个元素,在访问每个元素时,以该元素为起始元素,并向后寻找其最小长度的子数组,因此时间复制度为O()
而,题目所给的数组中所有元素均是正整数,因此每加上一个元素,子数组的和 sum 增加,通过这个特性,我们可以想到使用滑动窗口来解决这个问题
什么是滑动窗口?
滑动窗口是一种基于双指针的思想,两个指针指向的元素之间形成了一个窗口
因此滑动窗口是通过两个指针来维护的,那么如何移动这两个指针,是使用滑动窗口解决问题的关键

初始时,两个指针都指向0下标位置

遍历元素,若条件不满足,则将right指针向右移动,直到条件满足为止

当条件满足时,则保持右指针不变,开始移动左指针 left

在向窗口中添加新元素或从窗口中删除旧元素时,可能会更新一些与窗口范围有关的数据(例如,本题就需要更新最小子数组的长度)
如何使用滑动窗口解决本题?
(1)我们定义两个指针left right,并让其都指向数组首元素

(2)此时窗口内只有 2 这一个元素,不满足和 sum >= target,因此将right向右移动,将新的元素加入窗口中,并判断此时子数组的和 sum 是否大于等于target,若满足,则不再移动right

(3)在sum >= target时,首先判断最小的子数组长度是否需要更新,并保持right不变,向右移动左指针left,删除旧的元素,直到sum < target

(4)循环(2)(3),直到right遍历完数组
为什么可以使用滑动窗口解决本题?
因为我们要找的子数组是连续的,且数组中的元素都为正整数,即子数组中增加一个元素,子数组中的元素和sum增加,从窗口中删除一个元素,sum减小,因此我们可以通过改变子数组的两端元素来更新数组,因此可以使用滑动窗口来解决本题
由于左右指针都只遍历了一遍数组,因此时间复杂度为O(N)
滑动窗口代码
class Solution {public int minSubArrayLen(int target, int[] nums) {int left = 0;int right = 0;int sum = nums[0];int len = nums.length;int count = 0;while(left <= right && right < len){//小于目标值,向右移动右指针rightwhile(left <= right && right < len && sum < target){right++;if(right == len){break;}sum += nums[right];}//大于等于目标值while(left <= right && sum >= target){//更新目标值 由于count的初始值为0,因此需要更新初始值,否则最小值恒为0if((right - left) < count || count == 0){count = right - left + 1;}//左边值出窗口,left向右移动sum -= nums[left];left++;}}//若count未被更新,则返回0,即没有子数组的和大于target,//若count被跟新,则返回最小的子数组长度return count;}
}
题目来自:
LCR 008. 长度最小的子数组 - 力扣(LeetCode)
相关文章:
长度最小的子数组(Java详解)
目录 题目描述 题解 思路分析 暴力枚举代码 滑动窗口代码 题目描述 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条…...
计算机组成学习-数据的表示和运算总结
复习本章时,思考以下问题: 1)在计算机中,为什么要采用二进制来表示数据?2)计算机在字长足够的情况下能够精确地表示每个数吗?若不能,请举例说明。3)字长相同的情况下,浮点数和定点数的表示范围…...
目标检测YOLO系列从入门到精通技术详解100篇-【目标检测】机器视觉(基础篇)(八)
目录 前言 知识储备 机器视觉学习路线 视觉算法流程...
【4】基于多设计模式下的同步异步日志系统-框架设计
7. 日志系统框架设计 本项⽬实现的是⼀个多日志器日志系统,主要实现的功能是让程序员能够轻松的将程序运行日志信息落地到指定的位置,且⽀持同步与异步两种方式的日志落地方式。 项目的框架设计将项目分为以下几个模块来实现。 日志等级模块 日志等级模…...
Jupyter Markdown 插入图片
首先截图 注意 这一步是关键的!! 它需要使用电脑自带的截图,用qq啊vx啊美图秀秀那些都不行哦。 截图之后复制: 然后快捷键粘贴到jupyter里面,它会生成一段代码(没有代码就是说截图形式不对)&a…...
web自动化 -- pyppeteer
由于Selenium流行已久,现在稍微有点反爬的网站都会对selenium和webdriver进行识别,网站只需要在前端js添加一下判断脚本,很容易就可以判断出是真人访问还是webdriver。虽然也可以通过中间代理的方式进行js注入屏蔽webdriver检测,但…...
Java 数组另类用法(字符来当数组下标使用)
一、原因 看力扣的时候发现有位大佬使用字符来当数组下标使用。 class Solution {public int lengthOfLongestSubstring(String s) {int result 0;int[] hash new int[130];int i 0;for(int j 0; j < s.length(); j) {while(hash[s.charAt(j)] > 0) {hash[s.charAt…...
error转string
1 概述 在golang中,error类型是非常常见的一种数据类型。在开发过程中,经常会遇到需要将error类型转换成string类型的情况。本文主要介绍几种常见的golang error转string的方法。 2 使用Error()函数 在golang中,Error()函数是error类型的一…...
Android监听用户的截屏、投屏、录屏行为
Android监听用户的截屏、投屏、录屏行为 一.截屏 方案一:使用系统广播监听截屏操作 从Android Q(10.0)开始,Intent.ACTION_SCREEN_CAPTURED_CHANGED字段不再被支持。这是因为Google在安卓10 中引入了一个新的隐私限制&#…...
MATLAB算法实战应用案例精讲-【路径规划】 图搜索算法
目录 前言 几个高频面试题目 运动规划、路径规划、轨迹规划对比 1. 运动规划 2. 路径规划VS轨迹规划...
Elasticsearch-Kibana使用教程
1.索引操作 1.1创建索引 PUT /employee {"settings": {"index": {"refresh_interval": "1s","number_of_shards": 1,"max_result_window": "10000","number_of_replicas": 0}},"mappi…...
mysql(八)docker版Mysql8.x设置大小写忽略
Mysql 5.7设置大小写忽略可以登录到Docker内部,修改/etc/my.cnf添加lower_case_table_names1,并重启docker使之忽略大小写。但MySQL8.0后不允许这样,官方文档记录: lower_case_table_names can only be configured when initializ…...
KALI LINUX攻击与渗透测试
预计更新 第一章 入门 1.1 什么是Kali Linux? 1.2 安装Kali Linux 1.3 Kali Linux桌面环境介绍 1.4 基本命令和工具 第二章 信息收集 1.1 网络扫描 1.2 端口扫描 1.3 漏洞扫描 1.4 社交工程学 第三章 攻击和渗透测试 1.1 密码破解 1.2 暴力破解 1.3 漏洞利用 1.4 …...
vue之mixin混入
vue之mixin混入 mixin是什么? 官方的解释: 混入 (mixin) 提供了一种非常灵活的方式,来分发 Vue 组件中的可复用功能。一个混入对象可以包含任意组件选项。当组件使用混入对象时,所有混入对象的选项将被“混合”进入该组件本身的…...
[ffmpeg] find 编码器
背景 整理 ffmpeg 中,如何通过名字或者 id 找到对应编码器的。 具体流程 搜索函数 avcodec_find_encoder // 通过 ID 搜索编码器 avcodec_find_encoder_by_name // 通过名字搜索编码器源码分析 ffmpeg 中所有支持的编码器都会注册到 codec_list.c 文件中&…...
Android CardView基础使用
目录 一、CardView 1.1 导入material库 1.2 属性 二、使用(效果) 2.1 圆角卡片效果 2.2 阴影卡片效果 2.3 背景 2.3.1 设置卡片背景(app:cardBackgroundColor) 2.3.2 内嵌布局,给布局设置背景色 2.4 进阶版 2.4.1 带透明度 2.4.2 无透明度 一、CardView 顾名…...
云原生Kubernetes系列 | init container初始化容器的作用
云原生Kubernetes系列 | init container初始化容器的作用 kubernetes 1.3版本引入了init container初始化容器特性。主要用于在启动应用容器(app container)前来启动一个或多个初始化容器,作为应用容器的一个基础。只有init container运行正常后,app container才会正常运行…...
汽车电子芯片介绍之Aurix TC系列
Infineon的AURIX TC系列芯片是专为汽车电子系统设计的,采用了32位TriCore处理器架构。该系列芯片具有高性能、低功耗和丰富的外设接口,适用于广泛的汽车电子应用。以下是AURIX TC系列芯片的主要特性: 1. 高性能处理器 AURIX TC芯片采用了高…...
Linux 设置程序开机自启动的方法
目录 前言开机自启动参考 前言 CentOS Linux release 7.9.2009 (Core) 开机自启动 shell> vim /etc/rc.d/rc.local添加开机后执行的命令 sh /xxx/xxx.sh参考 https://www.cnblogs.com/xlmeng1988/archive/2013/05/22/3092447.html...
java企业财务管理系统springboot+jsp
1、基本内容 (1)搭建基础环境,下载JDK、开发工具eclipse/idea。 (2)通过HTML/CSS/JS搭建前端框架。 (3)下载MySql数据库,设计数据库表,用于存储系统数据。 (4…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
【HTTP三个基础问题】
面试官您好!HTTP是超文本传输协议,是互联网上客户端和服务器之间传输超文本数据(比如文字、图片、音频、视频等)的核心协议,当前互联网应用最广泛的版本是HTTP1.1,它基于经典的C/S模型,也就是客…...
Netty从入门到进阶(二)
二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架,用于…...
MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用
文章目录 一、背景知识:什么是 B-Tree 和 BTree? B-Tree(平衡多路查找树) BTree(B-Tree 的变种) 二、结构对比:一张图看懂 三、为什么 MySQL InnoDB 选择 BTree? 1. 范围查询更快 2…...
Chrome 浏览器前端与客户端双向通信实战
Chrome 前端(即页面 JS / Web UI)与客户端(C 后端)的交互机制,是 Chromium 架构中非常核心的一环。下面我将按常见场景,从通道、流程、技术栈几个角度做一套完整的分析,特别适合你这种在分析和改…...
jdbc查询mysql数据库时,出现id顺序错误的情况
我在repository中的查询语句如下所示,即传入一个List<intager>的数据,返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致,会导致返回的id是从小到大排列的,但我不希望这样。 Query("SELECT NEW com…...
《信号与系统》第 6 章 信号与系统的时域和频域特性
目录 6.0 引言 6.1 傅里叶变换的模和相位表示 6.2 线性时不变系统频率响应的模和相位表示 6.2.1 线性与非线性相位 6.2.2 群时延 6.2.3 对数模和相位图 6.3 理想频率选择性滤波器的时域特性 6.4 非理想滤波器的时域和频域特性讨论 6.5 一阶与二阶连续时间系统 6.5.1 …...
