算法——长度最小的子数组(leetcode209)

server/2024/11/13 15:35:33/

首先题目明确给出一个含有n个正整数的数组和一个目标值我们需要求出数组中下标连续的子数组元素之和大于等于目标值的最小子数组并返回。

明确题目大意后我们最容易想到的还是用两层for循环(外层for循环确定子数组的起始位置,内层for循环来确定终止位置并枚举起始位置至终止位置的数组的各种子数组的情况)然后筛选出符合题意的长度最小子数组并返回这种解法虽然思路较为简单但时间复杂度较高如果想要进一步优化时间复杂度的话我们可以使用滑动窗口的思想也就是双指针解法

双指针我们只需要使用一层for循环即可但要明确for循环中自增变量j的含义如果我们将j表示为起始位置的话那么求长度最小的子数组还是要遍历后续元素实质上和双层for循环是相似的所以我们将j定义为终止位置的指针,i表示起始位置的指针如果i至j这个子数组区间内的元素和大于等于目标值那么起始位置指针+1向右移动同时取符合条件的最小子数组的长度如此当for循环结束之后我们就可以得到长度最小的子数组长度并返回

class Solution {public int minSubArrayLen(int target, int[] nums) {int sum=0;int result=Integer.MAX_VALUE;int i=0;for (int j = 0; j < nums.length; j++) {sum+=nums[j];while(sum>=target){if(result>j-i+1){result=j-i+1;}sum-=nums[i];i++;}}return result==Integer.MAX_VALUE?0:result;}
}


http://www.ppmy.cn/server/141649.html

相关文章

共享汽车管理:SpringBoot框架的高效实现

摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了共享汽车管理系统的开发全过程。通过分析共享汽车管理系统管理的不足&#xff0c;创建了一个计算机管理共享汽车管理系统的方案。文章介绍了共享汽车管理系统的系…

【GIT】一文带你彻底了解 git rebase(图解+案例+实战)

文章目录 一、整合不同分支间的变更1. 功能原理2. 使用方法3. 使用场景&#xff1a;4. rebase VS merge4.1 异同4.2 优缺点4.3 小结 5. 工作流实战 二、重建提交历史1. 使用场景2.使用方法2.1 参数说明 3.工作流实战 三、git pull --rebase四、总结 git rebase&#xff0c;顾名…

新版IJidea 如何打开数据库窗口(2024.2.4 版)(连接数据库)

新版IJidea 2024.2.4 如何打开数据库窗口&#xff1f; 方式&#xff1a;使用插件&#xff0c;Database Navigator 1.安装插件&#xff0c;步骤如下&#xff1a; 打开 Settings/Preferences 对话框&#xff08;快捷键 CtrlAltS&#xff09;。前往 Plugins 菜单项。在搜索框中…

蓝桥杯:编程爱好者的试炼场

引言 蓝桥杯全国软件和信息技术专业人才大赛&#xff08;简称 “蓝桥杯”&#xff09;是中国大陆地区一项重要的计算机编程与软件设计赛事&#xff0c;旨在为在校学生提供展示编程能力的平台&#xff0c;以促进信息技术人才的培养和软件开发产业的发展。从2010年首届比赛开始&…

在配置环境变量之后使用Maven报错 : mvn : 无法将“mvn”项识别为 cmdlet、函数、脚本文件或可运行程序的名称。

最近&#xff0c;我在 Windows 系统上安装和配置 Apache Maven 时遇到了一些问题&#xff0c;想在此记录下我的解决历程&#xff0c;希望对遇到类似问题的朋友有所帮助。 问题描述 我下载了 Maven 并按照常规步骤配置了相关的环境变量。然而&#xff0c;在 PowerShell 中输入…

插入排序(C语言)

直接插入排序的基本思想&#xff1a;把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中&#xff0c;直到所有的记录插入完为止&#xff0c;得到一个新的有序序列 。 一、步骤 1.给定一个乱序的数组&#xff0c;如 从第一个元素开始排序&#xff0c;当只…

comfyUI官方笔记整理

官网教程笔记ComfyUI_examples 1.ComfyUI基础教程ComfyUI Basic Tutorial VN 从网上下载下来的模型ckpt和safetensors包含有3个不同的模型&#xff0c;CLIP&#xff0c;主模型还有VAEclip模型会和CLIPTextEncode进行连接&#xff0c;将文本编码为模型可以理解的向量形式。在S…

git之 revert和rebase

当我们想要回滚代码并保留之前的提交时 通过 git revert 需要回滚的提交单号" git rebase “目标分支" 如a分支开发&#xff0c;B是目标分支&#xff08;最终的远程上线分支) a 是基于B拉取的 当B有其他人提交之后 要将B的合入到a, 则需要在a 分支上执行 git reba…