当前位置: 首页 > 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…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility

Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程

STM32F1 本教程使用零知标准板&#xff08;STM32F103RBT6&#xff09;通过I2C驱动ICM20948九轴传感器&#xff0c;实现姿态解算&#xff0c;并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化&#xff0c;适合嵌入式及物联网开发者。在基础驱动上新增…...

go 里面的指针

指针 在 Go 中&#xff0c;指针&#xff08;pointer&#xff09;是一个变量的内存地址&#xff0c;就像 C 语言那样&#xff1a; a : 10 p : &a // p 是一个指向 a 的指针 fmt.Println(*p) // 输出 10&#xff0c;通过指针解引用• &a 表示获取变量 a 的地址 p 表示…...