leetcode 209. 长度最小的子数组(优质解法)

代码:

//时间复杂度 O(N) ,空间复杂度 O(1)
class Solution {
    //采用滑动窗口的方法解决
    public int minSubArrayLen(int target, int[] nums) {
        int numsLength=nums.length;
        int minLength=Integer.MAX_VALUE;
        int left=0;
        int right=0;
        int sum=0;

        while (right<numsLength){
            sum+=nums[right];
            while (sum>=target){
                //sum 符合要求
                //以当前 left 指针指向的数的最小子数组已经找到
                minLength=Math.min(minLength,right-left+1);
                sum-=nums[left++];
            }
            //sum 不符合要求
            right++;
        }

        if(minLength==Integer.MAX_VALUE){
            minLength=0;
        }
        return minLength;
    }
}

题解:

        该题我们可以采用滑动窗口的方法来解决,对于子数组,字串的题都经常用到滑动窗口的解决方法

        我们要想获得长度最小的子数组,首先就能够想到一种暴力方法,就是去获取数组中的所有子数组,再进行遍历找到符合条件且长度最小的子数组,而滑动窗口的解决方法是基于该思想实现的,但是进行了优化

        我们以题目中的示例 1 作为例子,输⼊: target = 7, nums = [2,3,1,2,4,3]

        1.首先我们用两个指针 L 和 R 指向下标为 0 的位置,用来进行遍历(它们两个遍历的规则不同),现在 L 和 R 指针之间便是我们此时要讨论的子数组,我们定义一个 sum 变量来表示此时子数组的长度,sum+= nums[ R ] ,此时子数组的和为 2 小于 target,所以我们需要扩大子数组

2        3        1        2        4        3

L

R

        2.将 R 指针向后移一位后,子数组的总和相比于之前多了 3,sum+= nums[ R ] =5 < target,于是我们还需要将 R 指针向后移,直到子数组的总和符合条件为止

2        3        1        2        4        3

L

          R

        3.当 R 指针一直移动到如下位置时,L 指针和 R 指针之间子数组的总和为 2+3+1+2 > target,符合条件,于是取变量 minLength 和当前子数组长度的最小值进行保存,由于这是得到的第一个最小长度,所以 minLength 记录此时的长度4,这里有个细节,记录此时的长度以后我们还需要让 R 指针继续向右移动吗 ?答案是不需要,因为我们已经获得了以 L 指针指向的数据为开头且符合条件的长度最小的子数组,当我们让 R 继续向右移动,由于 nums 是一个正整数的数组,所以得到的子数组是一定符合条件的,但是长度增加了 1 ,而我们要的是最小的子数组长度,这里长度增加 1 是完全没有必要的,所以肯定不会是我们要获取的答案

2        3        1        2        4        3

L

                              R

        4.以当前 L 指针为开头的最小子数组长度我们已经获取到了,所以可以让 L 指针向右移动,讨论以下一个数据为开头的最小子数组长度,sum -= nums[ L ] = 6,这里有个细节,我们需要让 R 指针回到 L 指针所在的位置进行遍历吗?答案是不需要,因为当 R 指针指向当前位置并且加上 L 指针之前指向的数据才符合要求,所以当 L 指针移动后,R指针至少要在当前位置才可能符合要求,此时 sum = 6 < target ,于是需要 R 指针向右移动扩大子数组的总和

2        3        1        2        4        3

          L

                              R

        5.接下来就是循环的操作了,当 R 指针指向 nums.length 的位置时循环结束

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/210385.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

详解原生Spring框架下的方法切入点表达式

&#x1f609;&#x1f609; 学习交流群&#xff1a; ✅✅1&#xff1a;这是孙哥suns给大家的福利&#xff01; ✨✨2&#xff1a;我们免费分享Netty、Dubbo、k8s、Mybatis、Spring...应用和源码级别的视频资料 &#x1f96d;&#x1f96d;3&#xff1a;QQ群&#xff1a;583783…

C++/Qt读写xml文件

今天介绍C/Qt如何读写xml文件&#xff0c;xml文件一般用于作为配置文件使用。 C C读写xml文件需要借助第三方来实现&#xff0c;比较好用的有tinyxml2和pugixml&#xff0c;对应的网址链接。 tinyxml2 pugixml 以tinyxml2为例&#xff0c;下载后进行解压可以看到以下文件&…

Python---格式化输出与%百分号----涉及转义符 \ 反斜杠的使用

相关链接Python--格式化输出中的转义符号----\t 制表符&#xff08;空格的&#xff09;和\n&#xff08;换行的&#xff09;_唯元素的博客-CSDN博客 Python---字符串&#xff08;用单、双引号、 三单/双引号定义。反斜杠 \ 转义&#xff0c;单在双内/双在单内 &#xff09;-CS…

【电路笔记】-串联和并联电阻

串联和并联电阻 文章目录 串联和并联电阻1、概述2、串联和并联电阻示例13、串联和并联电阻示例2 电阻器可以无限数量的串联和并联组合连接在一起&#xff0c;形成复杂的电阻电路。 1、概述 在之前的教程中&#xff0c;我们学习了如何将各个电阻器连接在一起以形成串联电阻器网…

混沌系统在图像加密中的应用(基于哈密顿能量函数的混沌系统构造1.5)

混沌系统在图像加密中的应用&#xff08;基于哈密顿能量函数的混沌系统构造1.5&#xff09; 前言一、自治非哈密顿系统的构造、动态特性分析1.相关理论基础2.两个四维自治非哈密顿系统3.数值分析 python代码 前言 续接混沌系统在图像加密中的应用&#xff08;基于哈密顿能量函…

重生奇迹MU再生原石

通过坎特鲁提炼之塔的NPC艾尔菲丝提炼成功就可以可获得再生宝石。 重生奇迹mu里的再生原石的用法&#xff1a; 1、打怪获得再生原石去提炼之塔&#xff08;进入坎特鲁遗址的141188位置的传送台&#xff09;。 2、找到&#xff08;艾儿菲丝&#xff09;把原石提炼成再生宝石。…

MySQL安全相关——TDE和数据脱敏功能介绍

MySQL作为一款广泛使用的开源关系型数据库管理系统(RDBMS)&#xff0c;其安全性一直是开发者和企业关注的重点。在MySQL中&#xff0c;有一些与安全相关的功能&#xff0c;其中包括Transparent Data Encryption(TDE)和数据脱敏。本文将对这些功能进行介绍。 一、Transparent Da…

深度学习实战63-利用自适应混合金字塔网络实现人脸皮肤美颜效果,快速部署与实现一键美颜功能

大家好,我是微学AI,今天给大家介绍一下深度学习实战63-利用自适应混合金字塔网络实现人脸皮肤美颜效果,快速部署与实现一键美颜功能。在本文中,我将介绍一种新颖的自适应混合金字塔网络(ABPN),该网络可以实现对超高分辨率照片的快速局部修饰。该网络主要由两个组件组成:一…

最简单的梅花吉凶表

以下是梅花易数吉凶表&#xff0c;使用方式&#xff1a; 随机报2组数字&#xff1a;第1个数除8得余数作为上爻&#xff0c;第2个数除8得余数作为下爻&#xff0c;然后对照以下表格&#xff0c;得到吉凶预测结果。 说明&#xff1a;经过个人不断实践&#xff0c;[大吉转大吉] …

基于STC12C5A60S2系列1T 8051单片机的液晶显示器LCD1602显示功能菜单应用

基于STC12C5A60S2系列1T 8051单片机的液晶显示器LCD1602显示功能菜单应用 STC12C5A60S2系列1T 8051单片机管脚图STC12C5A60S2系列1T 8051单片机I/O口各种不同工作模式及配置STC12C5A60S2系列1T 8051单片机I/O口各种不同工作模式介绍液晶显示器LCD1602简单介绍IIC通信简单介绍掉…

Android : SQLite 增删改查—简单应用

示例图&#xff1a; 学生实体类 Student.java package com.example.mysqlite.dto;public class Student {public Long id;public String name;public String sex;public int age;public String clazz;public String creatDate;//头像public byte[] logoHead;Overridepublic St…

分享一个判断曲线的趋势的Demo

需求背景 最近在处理数据&#xff0c;横坐标是时间&#xff0c;纵坐标是价格&#xff0c;需要判断一段时间内&#xff0c;由这些点绘制成的曲线的走势&#xff0c;比如趋势朝上&#xff0c;趋势朝下&#xff0c;水平调整这三种趋势。尝试了不少方法&#xff0c;下面这个效果还…

以热爱的态度对待生活,就是最自己的温柔

粉色系拼接款羽绒服 90白鸭绒&#xff0b;连帽立领设计 防风又保暖&#xff0c;柔软蓬松舒适感十足 衣服上加了时尚的字母印花元素 袖口做了魔术贴设计 下摆也做了可调节抽绳 防风保暖五部做到实处哦 宽松版型&#xff0c;很耐穿保暖性又很强 简单大方&#xff0c;搭配…

Flutter:视频下载案例

前言 最近在研究视频下载&#xff0c;因此打算一边研究一边记录一下。方便以后使用时查看。 使用到的库有&#xff1a; permission_handler 11.1.0 &#xff1a;权限请求 flutter_downloader 1.11.5&#xff1a;文件下载器 path_provider 2.1.1&#xff1a;路径处理 视频…

基于springboot 图书馆管理系统

qq&#xff08;2829419543&#xff09;获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;springboot 前端&#xff1a;采用vue技术开发 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xf…

网络编程之套接字

端口 && IP 在学习套接字编程之前&#xff0c;我们必须了解一下前缀知识。首先是IP和端口的作用。 在这之前&#xff0c;我们要明白一件事。那就是把数据从一台主机发送到另一台主机&#xff0c;是目的吗&#xff1f;&#xff1f;&#xff1f;当然不是&#xff01;&a…

Hdoop学习笔记(HDP)-Part.20 安装Flume

目录 Part.01 关于HDP Part.02 核心组件原理 Part.03 资源规划 Part.04 基础环境配置 Part.05 Yum源配置 Part.06 安装OracleJDK Part.07 安装MySQL Part.08 部署Ambari集群 Part.09 安装OpenLDAP Part.10 创建集群 Part.11 安装Kerberos Part.12 安装HDFS Part.13 安装Ranger …

java学习part27线程死锁

基本就是操作系统的内容 138-多线程-线程安全的懒汉式_死锁_ReentrantLock的使用_哔哩哔哩_bilibili

基于SpringBoot+Vue的前后端分离的房屋租赁系统2

✌全网粉丝20W,csdn特邀作者、博客专家、CSDN新星计划导师、java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取项目下载方式&#x1f345; 一、项目背景介绍&#xff1a; 开发过程中&#xff0…

基于Django框架搭建的协同过滤算法电影推荐网站-爬取的豆瓣电影数据

欢迎大家点赞、收藏、关注、评论啦 &#xff0c;由于篇幅有限&#xff0c;只展示了部分核心代码。 文章目录 一项目简介概述技术栈实现流程 二、功能三、系统四. 总结 一项目简介 # 电影推荐网站介绍 概述 该电影推荐网站是基于Django框架搭建的&#xff0c;旨在为用户提供个…