当前位置:网站首页>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
边栏推荐
- 线性代数感悟之1
- Generation of barcode and QR code
- Summary of common SQL statements
- El date picker limits the selection range from the current time to two months ago
- 给 el-dialog 增加拖拽功能
- 开期货,开户云安全还是相信期货公司的软件?
- Using quartz under. Net core -- operation transfer parameters of [3] operation and trigger
- 386. 字典序排数(中等)-迭代-全排列
- Baidu Map Case - Zoom component, map scale component
- [logical fallacy in life] Scarecrow fallacy and inability to refute are not proof
猜你喜欢
随机推荐
Deep understanding of control inversion and dependency injection
Using quartz under. Net core - [1] quick start
01 - get to know the advantages of sketch sketch
1-3 components and modules
Baidu Map 3D rotation and tilt angle adjustment
Basic case of Baidu map
EF core in ASP Generate core priority database based on net entity model
How to manually implement the mechanism of triggering garbage collection in node
1-1 NodeJS
Metaprogramming, proxy and reflection
386. 字典序排数(中等)-迭代-全排列
Qt error: /usr/bin/ld: cannot find -lGL: No such file or directory
Websocket (basic)
Signalr can actively send data from the server to the client
Understanding of RPC core concepts
The system cannot be started after AHCI is enabled
Come out after a thousand calls
给 el-dialog 增加拖拽功能
Shell-awk命令的使用
1-2 JSX syntax rules