209 | 长度最小的子数组

    写在前面～
    最近朋友面试遇到了这道题
    发来和小媛一起讨论的时候
    突然觉得说这是一道虽然简单，但是仍然可以讨论一下的「medium」题目
    决定发出来分享一下
    这道题有比较容易想到的「O（n） 时间复杂度」的解法
    但是难免有的面试官会＂精益求精＂
    进阶的询问是否有「O（n log（n）） 时间复杂度」的解法
    这就需要大家动动小脑瓜啦～（其实也不难想到）
    闲话少说～
    先来看题～
    题目
    给定一个含有 n 个正整数的数组和一个正整数 target 。
    找出该数组中满足 其和 ≥ target 的 长度最小的 连续子数组
    ［nums＿l， nums＿l＋1， ．．．， nums＿r－1， nums＿r］ ，
    并返回其长度。
    如果不存在符合条件的子数组，返回 0 。
    示例 1：
    输入：target ＝ 7， nums ＝ ［2，3，1，2，4，3］
    输出：2
    解释：子数组 ［4，3］ 是该条件下的长度最小的子数组。
    示例 2：
    输入：target ＝ 4， nums ＝ ［1，4，4］
    输出：1
    示例 3：
    输入：target ＝ 11， nums ＝ ［1，1，1，1，1，1，1，1］
    输出：0
    提示：
    1 ＜＝ target ＜＝ 109
    1 ＜＝ nums．length ＜＝ 105
    1 ＜＝ nums［i］ ＜＝ 105
    先停在这里
    思考一会儿～
    你会用什么方法呢
    一、滑动窗口 ／ 双指针
    思路：
    · 定义两个指针 start 和 end 分别表示子数组（滑动窗口窗口）的开始位置和结束位置
    · 维护变量 sum 存储子数组中的元素和
    · 初始状态下，start 和 end 都指向下标 0，sum 的值为 0
    · 每一轮迭代，将 nums［end］ 加到 sum，如果 sum≥s，则更新子数组的最小长度，然后将 nums［start］ 从 sum 中减去并将 start 右移，直到 sum＜s，在此过程中同样更新子数组的最小长度
    · 在每一轮迭代的最后，将 end 右移。
    复杂度分析：
    · 时间复杂度：O（n），其中 n 是数组的长度。指针 start 和 end 最多各移动 n 次。
    · 空间复杂度：O（1）。c
    
    二、前缀和 ＋ 二分查找
    思路：
    · 因为这道题保证了数组中每个元素都为正，所以前缀和一定是递增的，这一点保证了二分的正确性。如果题目没有说明数组中每个元素都为正，这里就不能使用二分来查找这个位置了。
    · 在确定每个子数组的开始下标后，找到长度最小的子数组需要 O（n） 的时间。
    · 如果使用二分查找，则可以将时间优化到 O（logn）。
    复杂度分析：
    · 时间复杂度：O（nlogn），其中 n是数组的长度。需要遍历每个下标作为子数组的开始下标，遍历的时间复杂度是 O（n），对于每个开始下标，需要通过二分查找得到长度最小的子数组，二分查找得时间复杂度是 O（logn），因此总时间复杂度是 O（nlon）。
    · 空间复杂度：O（n），其中 n 是数组的长度。额外创建数组 sums 存储前缀和。