当前位置:网站首页>209. 长度最小的子数组-滑动窗口
209. 长度最小的子数组-滑动窗口
2022-04-23 17:32:00 【hequnwang10】
一、题目描述
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
示例 1:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2:
输入:target = 4, nums = [1,4,4]
输出:1
示例 3:
输入:target = 11, nums = [1,1,1,1,1,1,1,1]
输出:0
二、解题
滑动窗口
这题使用滑动窗口,先使用右边界向右前进,当找到符合和大于target的下标值时,然后移动左边界。缩进左边界,找到最短的区间
class Solution {
public int minSubArrayLen(int target, int[] nums) {
//滑动窗口的思想
int left = 0,right = 0,length = nums.length;
int sum = 0;
int minLen = Integer.MAX_VALUE;
if(length == 0){
return 0;
}
while(right<length){
sum += nums[right];
while(sum >= target){
//移动左边界
minLen = Math.min(minLen,right-left+1);
sum -= nums[left];
left++;
}
right++;
}
return minLen == Integer.MAX_VALUE?0:minLen;
}
}
时间复杂度:O(n),其中 n 是数组的长度。指针 start 和 end 最多各移动 n 次。
空间复杂度:O(1)。
版权声明
本文为[hequnwang10]所创,转载请带上原文链接,感谢
https://blog.csdn.net/hequnwang10/article/details/124291203
边栏推荐
猜你喜欢
Compare the performance of query based on the number of paging data that meet the query conditions
嵌入式系统中,FLASH中的程序代码必须搬到RAM中运行吗?
Using quartz under. Net core -- general properties and priority of triggers for [5] jobs and triggers
RPC核心概念理解
For the space occupation of the software, please refer to the installation directory
Double pointer advanced -- leetcode title -- container with the most water
C语言函数详解
How to change input into text
Tdan over half
Qt error: /usr/bin/ld: cannot find -lGL: No such file or directory
随机推荐
JVM class loading mechanism
古代埃及希腊,数学用的什么进制
Detailed explanation of C webpai route
For the space occupation of the software, please refer to the installation directory
EF core in ASP Generate core priority database based on net entity model
Double pointer advanced -- leetcode title -- container with the most water
RPC核心概念理解
tidb-server 的配置文件在哪里?
Self use learning notes - connectingstring configuration
给 el-dialog 增加拖拽功能
Shell-awk命令的使用
. net cross platform principle (Part I)
Learning record of uni app dark horse yougou project (Part 2)
Understanding of RPC core concepts
Signalr can actively send data from the server to the client
[logical fallacy in life] Scarecrow fallacy and inability to refute are not proof
练习:求偶数和、阈值分割和求差( list 对象的两个基础小题)
Qt error: /usr/bin/ld: cannot find -lGL: No such file or directory
How to manually implement the mechanism of triggering garbage collection in node
【WPF绑定3】 ListView基础绑定和数据模板绑定