算法学习篇四:滑动窗口
声明
本文旨在记录自己学习算法期间对相关知识的理解与运用,因为博主也是学习者,如有与其他文章相同的地方,还望理解。创作不易,点赞+关注,支持支持博主,万分感谢!
题目 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组
[numsl, numsl+1, ..., numsr-1, numsr] ,
并返回其长度。如果不存在符合条件的子数组,返回 0 。
示例 1:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
解法一
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int sum=0;
int length=0;
int result_length=INT32_MAX;
for(int i=0;i<nums.size();i++)
{
sum=0;
for(int j=i;j<nums.size();j++)
{
sum+=nums[j];
if(sum>=target)
{
length=j-i+1;
result_length=result_length<length ? result_length : length;
break;
}
}
}
return result_length == INT32_MAX ? 0 : result_length;
}
};
解法一思路
示例 1:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
以这个例子来进行思路解释,在理解题目的基础上,因为要找出比目标值大,但长度最小,连续的子数组,所以必然需要遍历数组,在每次遍历数组时就需要对每次遍历的数据元素进行累加,并将累加值与目标值进行比较,并将累加的数组元素的个数进行记录(也就是子数组的长度)。但是需要每次都和前一次的子数组元素进行比较,记录最短且连续的字数组,并作为返回值。
所以
**第一步:我们就需要用两层for循环,第一层for循环用来遍历输入数组,第二层for循环用来进行数组元素的累加,并且每累加一个数组元素,所以算法里 for(int i=0;i<nums.size();i++); for(int j=i;j<nums.size();j++)。需要从当前元素向后累加。但是上一个数组元素的累加值不能影响下一个元素向后进行累加,所以需要SUM=0;**将累加值进行清零。
**第二步:接下来,就需要在循环体内就需要将累加值与目标值进行比较,然后记录当前满足条件的子数组的长度,也就是length=j-i+1;**然后更新最后输出的值。这里说一下这句代码的意思。具体可见拓展知识点1。
result_length=result_length<length ? result_length : length; ( int result_length=INT32_MAX; ) INT32_MAX 可以把它认为在limits.h下面的一个宏,反正数值很大就对了。如果初始值为0,那<判断条件就不成立了。
解法二 滑动窗口
首先对于滑动窗口的理解:
窗口也就是当前计算累加值的子数组,
窗口的起始位置也就是不断改变的子数组的起始数组元素,
窗口的终止位置就是不断改变的子数组的末尾数组元素。
滑动也就是子数组的数组元素在不断改变。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int i=0;//滑动窗口的起始位置
int j=0;//滑动窗口的终止位置
int length=0;// 滑动窗口的长度
int result_length=INT32_MAX;
int sum=0;
for(j=0;j<nums.size();j++)
{
sum=sum+nums[j];
while(sum>=target)
{
length=j-i+1;
result_length=result_length<length?result_length:length;
sum =sum-nums[i];
i++;
}
}
return result_length == INT32_MAX?0:result_length;
}
};
解法二思路
示例 1:
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。
用举例子的方式或许更加容易理解,i,j的起始都是2,i是窗口的起始位置,j是窗口的终止位置, for(j=0;j<nums.size();j++) ,就是用来遍历整个数组,然后将值进行累加,如果介于i与j之间的数组元素累加和大于目标值,则记录i与j之间子数组的长度,也就是滑动窗口的长度,因为大于目标值,所以需要将窗口的起始位置向后移,即 i++; ,同时累加和需要减去nums[i]。 sum =sum-nums[i]; 。与解法一相比,就不需要sum=0;来清零。
然后就是 随着遍历数组的推进,然后不断改变滑动窗口的起始位置 ,直至遍历结束。
拓展知识点
1. 程序设计中?与:的使用
“?” 在C语言中表示疑问的意思;“:” 在C语言中表示判断的结果选择,二者同时出现,两者组成结构选择语句。使用方法如下:<表达式1>?<表达式2>:<表达式3>
在运算中,首第一个表达式进行检验,如果为真,则返回表达式2的值;如果为假,则返回表达式3的值。
2. i++与++i的使用区别
博主就不多赘述了,详见这篇文章
说明
博主尽力描述的更好理解些,有些地方难免有问题,欢迎批评指正。