当前位置:网站首页>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
边栏推荐
- 双闭环直流调速系统matlab/simulink仿真
- Qt error: /usr/bin/ld: cannot find -lGL: No such file or directory
- Use of shell cut command
- The system cannot be started after AHCI is enabled
- Webapi + form form upload file
- . net type transfer
- ASP. Net core configuration options (Part 1)
- [C#] 彻底搞明白深拷贝
- Perception of linear algebra 2
- Understanding and small examples of unity3d object pool
猜你喜欢
In embedded system, must the program code in flash be moved to ram to run?
Perception of linear algebra 2
MySQL installation
440. 字典序的第K小数字(困难)-字典树-数节点-字节跳动高频题
练习:求偶数和、阈值分割和求差( list 对象的两个基础小题)
. net type transfer
索引:手把手教你索引从零基础到精通使用
Using quartz under. Net core -- operation transfer parameters of [3] operation and trigger
Webapi + form form upload file
Qt error: /usr/bin/ld: cannot find -lGL: No such file or directory
随机推荐
读《Software Engineering at Google》(15)
Self use learning notes - connectingstring configuration
Read software engineering at Google (15)
[batch change MySQL table and corresponding codes of fields in the table]
Using quartz under. Net core -- job attributes and exceptions of [4] jobs and triggers
Further optimize Baidu map data visualization
JS to find the character that appears three times in the string
Some problems encountered in recent programming 2021 / 9 / 8
MySQL installation
Change Oracle to MySQL
01-初识sketch-sketch优势
Double pointer advanced -- leetcode title -- container with the most water
练习:求偶数和、阈值分割和求差( list 对象的两个基础小题)
Promise (I)
STM32 entry development board choose wildfire or punctual atom?
Node template engine (EJS, art template)
How to manually implement the mechanism of triggering garbage collection in node
Compare the performance of query based on the number of paging data that meet the query conditions
開期貨,開戶雲安全還是相信期貨公司的軟件?
Tdan over half