当前位置: 首页 > news >正文

长度最小的子数组(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(^{_N{2}})

而,题目所给的数组中所有元素均是正整数,因此每加上一个元素,子数组的和 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] &#xff0c;并返回其长度。如果不存在符合条…...

计算机组成学习-数据的表示和运算总结

复习本章时&#xff0c;思考以下问题&#xff1a; 1)在计算机中&#xff0c;为什么要采用二进制来表示数据&#xff1f;2)计算机在字长足够的情况下能够精确地表示每个数吗&#xff1f;若不能&#xff0c;请举例说明。3)字长相同的情况下&#xff0c;浮点数和定点数的表示范围…...

目标检测YOLO系列从入门到精通技术详解100篇-【目标检测】机器视觉(基础篇)(八)

目录 前言 知识储备 机器视觉学习路线 视觉算法流程...

【4】基于多设计模式下的同步异步日志系统-框架设计

7. 日志系统框架设计 本项⽬实现的是⼀个多日志器日志系统&#xff0c;主要实现的功能是让程序员能够轻松的将程序运行日志信息落地到指定的位置&#xff0c;且⽀持同步与异步两种方式的日志落地方式。 项目的框架设计将项目分为以下几个模块来实现。 日志等级模块 日志等级模…...

Jupyter Markdown 插入图片

首先截图 注意 这一步是关键的&#xff01;&#xff01; 它需要使用电脑自带的截图&#xff0c;用qq啊vx啊美图秀秀那些都不行哦。 截图之后复制&#xff1a; 然后快捷键粘贴到jupyter里面&#xff0c;它会生成一段代码&#xff08;没有代码就是说截图形式不对&#xff09;&a…...

web自动化 -- pyppeteer

由于Selenium流行已久&#xff0c;现在稍微有点反爬的网站都会对selenium和webdriver进行识别&#xff0c;网站只需要在前端js添加一下判断脚本&#xff0c;很容易就可以判断出是真人访问还是webdriver。虽然也可以通过中间代理的方式进行js注入屏蔽webdriver检测&#xff0c;但…...

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中&#xff0c;error类型是非常常见的一种数据类型。在开发过程中&#xff0c;经常会遇到需要将error类型转换成string类型的情况。本文主要介绍几种常见的golang error转string的方法。 2 使用Error()函数 在golang中&#xff0c;Error()函数是error类型的一…...

Android监听用户的截屏、投屏、录屏行为

Android监听用户的截屏、投屏、录屏行为 一.截屏 方案一&#xff1a;使用系统广播监听截屏操作 ​ 从Android Q&#xff08;10.0&#xff09;开始&#xff0c;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内部&#xff0c;修改/etc/my.cnf添加lower_case_table_names1&#xff0c;并重启docker使之忽略大小写。但MySQL8.0后不允许这样&#xff0c;官方文档记录&#xff1a; lower_case_table_names can only be configured when initializ…...

KALI LINUX攻击与渗透测试

预计更新 第一章 入门 1.1 什么是Kali Linux&#xff1f; 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是什么&#xff1f; 官方的解释&#xff1a; 混入 (mixin) 提供了一种非常灵活的方式&#xff0c;来分发 Vue 组件中的可复用功能。一个混入对象可以包含任意组件选项。当组件使用混入对象时&#xff0c;所有混入对象的选项将被“混合”进入该组件本身的…...

[ffmpeg] find 编码器

背景 整理 ffmpeg 中&#xff0c;如何通过名字或者 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 内嵌布局&#xff0c;给布局设置背景色 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系列芯片是专为汽车电子系统设计的&#xff0c;采用了32位TriCore处理器架构。该系列芯片具有高性能、低功耗和丰富的外设接口&#xff0c;适用于广泛的汽车电子应用。以下是AURIX TC系列芯片的主要特性&#xff1a; 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、基本内容 &#xff08;1&#xff09;搭建基础环境&#xff0c;下载JDK、开发工具eclipse/idea。 &#xff08;2&#xff09;通过HTML/CSS/JS搭建前端框架。 &#xff08;3&#xff09;下载MySql数据库&#xff0c;设计数据库表&#xff0c;用于存储系统数据。 &#xff08;4…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

基于PHP的连锁酒店管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...