我爱学算法之——滑动窗口攻克子数组和子串难题（上）

现在来学习"滑动窗口"这一算法思想。

至于什么是"滑动窗口"呢？简单来说就是同向双指针；现在来通过题目来了解什么是"滑动窗口"

一、长度最小的子数组

题目链接：长度最小的子数组

题目解析

先来看题目，给了一个数组nums和一个整数target，让我们找到nums的一个满足条件（条件：子数组的和大于target）的最长子数组。

算法思路

首先第一次看到子数组/子串问题的算法题，能想到的思路就肯定是暴力枚举了；现在就先来看暴力枚举如何解决的。

暴力枚举

我们依次枚举整个数组的每一个子数组，并判断是否满足条件；满足条件且长度小于最总结果，就更新最终结果。

上面意思呢？

暴力解法的大致思路如上述所示；现在来看一下暴力枚举有哪些操作是不必要的

当right第一次找到满足条件的位置并更新结果后，left++，right从left位置再重新遍历

这个操作感觉有些多余了，因为我们right遍历时第一次遇到满足条件的就停了下来；

如果right从left++后的位置开始再遍历到上次满足条件位置的位置，这一个遍历过程很多余；

什么意思呢？

就以暴力枚举中的示例来说：

right第一次遍历到下标为3位置恰好满足条件；此时区间是[0,3]，我们更新结果之后，left++

right从下标为1的位置开始再次遍历；

我们直到[0,3]区间刚满足条件，那区间[1,1]和[1,2]是一定不满足条件的[1,3]才有可能满足条件。

那这样我们就可以想办法省略这个不必要的步骤：

找到满足条件的区间，并更新结果并lef++后，如何去解决right重新遍历的问题？

解决问题，我们要找到问题的本质：

**暴力枚举**中为什么要重新进行遍历，本质问题就是我们不知道left++后，区间[left,right]的和；（所以暴力枚举才会进行重新遍历）

那我们现在定义一个变量sum来实时记录区间[left,right]的和，这样不就不需要重新遍历了吗。

我们只需要在right向后遍历和left更新时，顺手更新一下sum的值就可以了。

滑动窗口

其实滑动窗口就是优化了暴力枚举解法中不必要的部分

知道了如何去解决暴力枚举中不必要的问题，现在来实现

通过上图所示推到，我们的想法是可行的，现在来看整体的一个思路

滑动窗口，为什么称为滑动窗口？

就是right和left在遍历更新的过程中维护了一段区间[left , right]，这个区间像窗口一样在数组中滑动。

现在来看实现这个问题的一个整体思路：

进窗口：让right向右遍历，更新区间[left , right]的和sum；称为进窗口（就是让right遍历到的元素进入（窗口）区间内。出窗口：如果当前区间满足条件（区间和大于target)，就更新结果，然后让left++，并更新区间[left , right]的和；重复上述操作直到区间不满足条件。更新结果：至于什么时候更新结果，每一道题都不一样，根据题目中的要求再决定什么时候更新结果。

代码实现

classSolution{ public:intminSubArrayLen(int target