数组part02

209.长度最小子数组

这道题的是滑动窗口的入门题目。一开始使用的是暴力解法，使用了双层嵌套的for循环，外层循环控制遍历的起始位置，内层循环控制遍历的结束位置，然后去搜索每个可能的子数组，判断其是否满足条件。但是现在在leetcode这么提交代码已经超时了。

滑动窗口的思想是，使用一次for循环去做两次for循环做的事，让for循环指向结束位置end，初始值为0，并不断移动end的位置。定义一个变量start指向起始位置，start的初始值为0。当向后移动end时，会把整个窗口里的值加到变量sum里。当sum>=target时，证明找到了一个子窗口，但是会继续向后移动起始位置start，以寻找一个大于target的最小子数组。每向后遍历一个start，都会将sum里对应的值减去，直到sum>=target的条件不满足位置。

需要注意的是：滑动窗口和暴力解法的区别在哪里？

如果按照结尾的索引end来搜索，对于每一个end，暴力搜索就是把start从0到end都搜索了一遍。 而滑动窗口的方法中，对于每一个end，剪枝掉的部分是:

1. start过大的部分，如果有一个start都不满足条件了，那么更大的start更不可能满足，自然没必要继续start++了。

2. start过小的部分，而为什么start不能从头开始找这件事，因为以end为结尾，更小的start也可能会满足sum>=target的条件，凭什么这部分不进行搜索呢？答：当我们增加end的时候，直到再一次遇到符合条件的最小滑动窗口的时候，end至少增加了1，start也相比上一次满足条件增加了1(相当于长度相比上一次满足条件至少是不变的)，这个时候如果让start回头，确实可以遇到符合条件的滑动窗口，但是这个滑动窗口一定会比之前遇到的长至少1个单位。