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循环里的索引。

解题的关键在于 窗口的起始位置如何移动,如图所示:

leetcode_209

可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况,不断调节子序列的起始位置。从而将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)

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

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

相关文章

Java实现查找文件

1 问题 如何利用java来查找文件&#xff1f; 2 方法 2.1定义一个查找类&#xff0c;设置两个参数&#xff08;查找的目录和文件后缀名&#xff09;&#xff0c;然后判断文件夹是否为空 2.2 判断是否是文件夹&#xff0c;如果是文件夹则将里面的文件放入数组进行遍历&#xff08…

【Python零基础学习入门篇①】——基本语法与变量

⬇️⬇️⬇️⬇️⬇️⬇️ ⭐⭐⭐Hello&#xff0c;大家好呀我是陈童学&#xff0c;一个普通大一在校生&#xff0c;请大家多多关照呀嘿嘿&#x1f601;&#x1f60a;&#x1f618; &#x1f31f;&#x1f31f;&#x1f31f;技术这条路固然很艰辛&#xff0c;但既已选择&#x…

Redis 事务相关操作

Redis 作为一个非关系型内存数据库&#xff0c;也有事务定义 1. 事务的定义-ACID特性 A表示原子性&#xff1a;即事务是一个不可分割的实体&#xff0c;事务中的操作要么都完成&#xff0c;要么都不完成 C表示一致性&#xff1a;即事务前后数据完整性必须一致&#xff0c;假…

基于springboot实现数码论坛系统设计与实现演示【附项目源码+论文说明】

基于springboot实现数码论坛系统设计与实现演示开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/idea Maven…

Jieba分词的准确率提升:使用paddle模式进行分词(使用百度飞桨深度学习模型进行分词)

1 Paddle模式简介 jieba中的paddle模式是指使用飞桨&#xff08;PaddlePaddle&#xff09;深度学习框架加速分词的一种模式。相对于传统的分词算法&#xff0c;paddle模式采用了深度学习模型&#xff0c;可以获得更高的分词准确度和更快的分词速度。 paddle模式是基于卷积神经…

数据分析之Pandas(2)

3.Pandas 文章目录3.Pandas3.3 Pandas进阶3.3.1 数据重塑和轴向旋转&#xff08;1&#xff09;层次化索引Series的层次化索引DataFrame的层次化索引层次化——电影数据示列&#xff08;2&#xff09;数据旋转3.3.2 数据分组、分组运算3.3.3 离散化处理3.3.4 合并数据集&#xf…

使用langchain打造自己的大型语言模型(LLMs)

我们知道Openai的聊天机器人可以回答用户提出的绝大多数问题,它几乎无所不知&#xff0c;无所不能&#xff0c;但是由于有机器人所学习到的是截止到2021年9月以前的知识&#xff0c;所以当用户询问机器人关于2021年9月以后发送的事情时&#xff0c;它无法给出正确的答案&#x…

【Java 21 新特性 】顺序集合(Sequenced Collections)

Java 21 中增加了一种新的集合类型&#xff1a;顺序集合&#xff08;Sequenced Collections&#xff09;。要介绍顺序集合&#xff0c;就首先要说明一下出现顺序&#xff08;encounter order&#xff09;。出现顺序指的是在遍历一个集合时&#xff0c;集合中元素的出现顺序。有…

Redis高频40问

Redis连环40问&#xff0c;绝对够全&#xff01; Redis是什么&#xff1f; Redis&#xff08;Remote Dictionary Server&#xff09;是一个使用 C 语言编写的&#xff0c;高性能非关系型的键值对数据库。与传统数据库不同的是&#xff0c;Redis 的数据是存在内存中的&#xf…

Python:每日一题之《全排列的价值》真题练习

问题描述 对于一个排列 A(a1​,a2​,⋯,an​), 定义价值 ci​ 为 a1​ 至 ai−1​ 中小于 ai​ 的数 的个数, 即 。 ci​∣{aj​∣j<i,aj​<ai​}∣。 ​ 定义 A 的价值为 ∑i1n​ci​ 。 给定 n, 求 1 至 n 的全排列中所有排列的价值之和。 输入格式 输入一行包含…

SpringBoot(五) Docker

一、简介 Docker是一个开源的应用容器引擎&#xff1b; Docker支持将软件编译成一个镜像&#xff1b;然后在镜像中各种软件做好配置&#xff0c;将镜像发布出去&#xff0c;其他使用者可以直接使用这个镜像。 运行中的这个镜像称为容器&#xff0c;容器启动是非常快速的。类似…

HTB-soccer

信息收集 22 ssh80 http9091 对80进行检查。 搜索得知存在默认登陆密码admin:admin123 和 user:12345。 右上角有一个upload&#xff0c;试试能不能本地上传。 能够获取上传的路径&#xff0c;但是此文件没有写入权限。 切换到tiny文件夹再次上传。 在/tiny/uploads能够…

文心一言,被网友玩坏了哈哈哈哈哈哈哈

现在人工智能正火&#xff0c;百度“文心一言”出来&#xff0c;虽然只是小范围测试&#xff0c;但已经被玩坏了&#xff01;这应该算是卖全羊送狗肉娃娃…菜…也没毛病哈看来对美女还有些误解虎头虎脑的胖大胖小子哈哈哈哈哈鸳鸯和锅都有&#xff0c;还不满意吗什么奇行种似乎…

数据结构和算法(3):递归

目录概述单路递归 Single Recursion多路递归 Multi Recursion递归优化-记忆法递归时间复杂度-Master theorem递归时间复杂度-展开求解概述 定义 计算机科学中&#xff0c;递归是一种解决计算问题的方法&#xff0c;其中解决方案取决于同一类问题的更小子集 In computer scien…

情感语音转换学习

情感语音转换&#xff08;Emotional Voice conversion&#xff09; 言语不仅仅是词汇&#xff0c;它承载着说话者的情感。之前的研究(Mehrabian和Wiener, 1967)表明&#xff0c;在交流情感和态度时&#xff0c;口头语言只传达了7%的信息&#xff0c;非语言的声音属性(38%)和面…

简单研究一下 OpenAI 的官方文档

文档地址&#xff1a;https://platform.openai.com/docs/ 接口说明&#xff1a;https://platform.openai.com/docs/api-reference 一、概览 OpenAI API 可直接调用模型接口&#xff0c;也可在线微调&#xff08;不过只能微调GPT-3系列模型&#xff09;。 本小节主要介绍 toke…

定长内存池的实现

文章目录 什么是内存池 池化技术内存池内存池主要解决的问题malloc定长内存池的实现前言 当前项目是实现一个高并发的内存池&#xff0c;他的原型是Google的一个开源项目tcmalloc&#xff0c;tcmalloc全称Thread-Caching Malloc&#xff0c;即线程缓存的malloc&#xff0c;实现…

python用户价值分析

数据获取&#xff1a; 表格数据 数据清洗后数据&#xff1a;链接&#xff1a;https://pan.baidu.com/s/1D7qOZqKmF3YR3meQPsp3sQ 提取码&#xff1a;1234 数据下载下来后&#xff0c;先进行数据清洗。数据清洗在进行用户价值分析,也可以直接下载我清洗后的数据。 RFM模型&a…

springcloud微服务架构搭建过程

项目地址&#xff1a;源代码 仅作为学习用例使用&#xff0c;是我开发过程中的总结、实际的一部分使用方式 开发环境&#xff1a; jdk11 springboot2.7.6 springcloud2021.0.5 alibabacloud 2021.0.4.0 redis6.0 mysql8.0 一、项目搭建 wdz-api&#xff1a;存放远程服务调用相关…

如何选电脑

1、CPU&#xff08;中央处理器&#xff09; 怎么看CPU型号&#xff1a;CPU:系列-代数等级核心显卡型号电压后缀 例如CPU:i7-10750H &#xff1a; 1、系列&#xff1a;Intel的酷睿i3、i5、i7、i9这四个系列的CPU&#xff0c;数字越大就代表越高端。 2、代数&#xff1a;代表…