每日一练【长度最小的子数组】
2023-12-16 14:29:00
一、题目描述
给定一个含有?n
?个正整数的数组和一个正整数?target
?。
找出该数组中满足其总和大于等于?target
?的长度最小的?连续子数组?[numsl, numsl+1, ..., numsr-1, numsr]
?,并返回其长度。如果不存在符合条件的子数组,返回?0
?。
二、题目解析
经过观察示例,我们发现一个规律就是:比如示例1,2,3,1,2私塾相加之和大于target,这时如果再让右指针向右移动肯定是大于7,并且长度一定不是最小的,所以我们规避这样的情况,去让左指针++,先判断是否已经大于7,如果不大于那让右指针++,然后一直重复上述操作!
这时发现做右指针都向同一个方向移动,我们就称呼该算法就是“滑动窗口”!
三、原码
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums)
{
int len = nums.size();
int min = 0;
int left = 0;
int right = 0;
int sum = nums[0];
while(left<len && right<len)
{
if(sum < target)
{
right++;
//判断特殊越界的情况
if(right == len)
break;
sum += nums[right];
}
else
{
if(min == 0)
min = right-left+1;
else
{
if(right-left+1 < min)
min = right-left+1;
}
sum -= nums[left];
left++;
}
}
return min;
}
};
文章来源:https://blog.csdn.net/hanwangyyds/article/details/134927690
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!