算法题（33）：长度最小的子数组

审题:

需要我们找到满足元素之和大于等于target的最小子数组的元素个数，并返回

思路：

核心：子数组共有n种起点，nums数组的每个元素都可以充当子数组的首元素，我们只需要先确定子数组的首元素，然后往后查找满足条件的最小下标，最后维护一个minsize即可

方法一：双层for循环

我们的第一层循环确定子数组首元素，然后第二层循环寻找满足条件的下标，并维护minsize。这个方法虽然简单，但是时间复杂度是O（N^2），会超时

方法二：前缀和 + 二分查找

二分查找的时间复杂度是logN，如果结合for循环和二分查找可以把时间复杂度优化到

O（N*longN）

!:题目说了所有数据都是正整数，所以前缀和一定是递增的，可以用二分

不过二分查找只能根据一个确定的值去找，所以我们要把求和预处理了，也就是先计算前缀和。

确定首元素和方法一一样，都是用一个for循环，然后二分查找大于等于target的第一个位置bound。

target是多少？

bound位置的前缀和减第i-1个元素的前缀和得到的就是第i-1个元素和bound位置元素之间的和，若该和大于等于s，则满足条件

所以有：target = s + sum[i-1]

而此时的子数组长度为bound - (i-1)

方法三:滑动窗口

优化前面两个方法，该方法时间复杂度为O（N）

我们创建一个start指针和一个end指针，一开始都指向nums首元素，其中start指针指向的是子数组的首元素，end指向的是子数组最后一个元素，维护minsize记录最小长度

解题：

方法二：前缀和 + 二分查找

sum[i]:表示的是前i个元素的前缀和

子数组的首和尾分别是第bound个数据和第i个数据，所以子数组size是bound-(i-1)

特殊处理：在return处，三目运算符的用处是处理没找到满足的子数组的情况，返回0

注意：sum.end()表示的不是最后一个有效数据的地址，而是其下一个地址，且此地址只有没找到bound才会返回

方法三：滑动窗口

其实方法三的核心也是通过每个子数组的首元素去运算。

当当前的sum不满足要求，就让end接着往下走

遇到满足要求就记录size并且让start++（这一步相当于start位置为首元素的子数组最小的size已经计算完了），但是因为不确定start++后是否仍满足，所以这里设置成循环

209. 长度最小的子数组 - 力扣（LeetCode）