不要相信，我真的救了你

给出含有

题目209.长度最小的子数组

个正整数的数组和正整数s，在该数组中找出满足其和s的长度最小的连续子数组，并返回其长度。 如果不存在满足条件的子数组，则返回0。

示例：输入： s=7，nums=[ 2，3，1，2，4，3 ]输出： 2解释：部分数组[ 4，3 ]是在此条件下长度最小的部分数组。

暴力解法

这个主题的暴力解法当然是两个for循环，然后继续寻找符合条件的子序列，时间复杂度显然是o(n^2)。

代码如下所示。

类解决方案{2}

公共：

intminsubarraylen(ints，vectorintnums ) {

int结果=int 32 _最大值； //最终结果

intsum=0； //子序列的数值之和

intsubLength=0； //子序列的长度

for (英制=0； inums.size (； I )//将子序列的起点设为I

sum=0；

for(intj=I； jnums.size (； 将j )//子序列的结束位置设为j

求和=数字；

如果发现超过了if(sum=s )//子序列和s，则更新result

subLength=j-i 1； //取子序列的长度

结果=结果？ 结果：子长度；

布莱克； //我们正在寻找满足条件的最短的子序列，所以如果满足条件就会中断

}

}

}

如果没有给result赋值，则返回0，表示没有符合条件的子序列

返回结果==int 32 _ max？ 0:结果；

}

(；

时间复杂度： o(n )2)空间复杂度： o )1)

滑动窗口

下面就数组操作中的另一个重要方法“滑动窗口”进行说明。

滑动窗口是指“不断调节子序列的开始位置和结束位置，得出我们想考虑的结果”。

这里也是主题的例子，s=7，排列为2、3、1、2、4、3，让我们来看看寻找的过程。

最后找到4、3是最短的距离。

实际上从视频中发现滑动窗口也可以理解为双指针法的一种！ 但是，由于该解法类似于移动窗口，因此称为滑动窗口比较合适。

正题要实现滑动窗口，主要确定以下三点。

窗户里是什么？ 怎么移动窗口的开始位置？ 怎么移动窗口的结束位置？ 窗口是指满足其和s的长度最小的连续部分数组。

的开始位置如何移动：如果当前窗口的值大于s，则窗口将向前移动(即必须缩小)。

窗口的结束位置怎么移动？ 窗口的结束位置是遍历数组的指针，窗口的开始位置设定为数组的开始位置即可。

解决问题的关键是窗口的开始位置如何移动，如图所示。

“滑动窗口的优点是根据当前子序列和大小的情况，不断调整子序列的开始位置。 由此，将O(N )2)的暴力解法降级为o ) n )。 “”

C++滑动窗口代码

类解决方案

公共：

intminsubarraylen(ints，vectorintnums ) {

int结果=int 32 _最大值；

intsum=0； //滑动窗口的数值之和

英特尔=0； //滑动窗口的原始位置

intsubLength=0； //滑动窗口的长度

for(intj=0； jnums.size (； j ) {2}

求和=数字；

//这里使用while，每次更新I (开始位置)，持续比较子序列是否满足条件，这点要注意

wile (和=s ) {

sublength=(j-I1)； //取子序列的长度

结果=结果？ 结果：子长度；

求和-=数字； //这里出现滑动窗口的精髓，不断改变I (子序列的开始位置)

}

}

如果没有给result赋值，则返回0，表示没有符合条件的子序列

返回结果==int 32 _ max？ 0:结果；

}

(；

时间复杂度： o(n )空间复杂度： o )1) )。

在留言区留下你的想法吧！

--------- -结束-------

关于算法学习的资料总结在github:https://github.com/young yangyang 04/leet代码- master中。 其中还有leet代码刷题攻略、各类型经典主题刷题顺序、思维导图。 看看就一定会得到。

每天8:35小时推送经典算法主题，推送的所有主题不是孤立的，而是浅而深、环环相扣的，梳理算法知识脉络，轻松学习算法！

@代码随想录期待着你的关注！