力扣题：209. 长度最小的子数组

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

给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 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

进阶：
如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
思路和算法：
方案一：暴力解法
这道题目暴力解法当然是 两个for循环，然后不断的寻找符合条件的子序列，时间复杂度很明显是$O(n^2)$。并且这也是我的笨蛋脑瓜子一开始只能想到的办法。
代码（c++）：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int len = 0;    //符合条件的子数组的长度
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            int sum = 0;    //和
            for (int j = i; j < n; ++j) {
                sum += nums[j];
                if (sum >= target && (len == 0 || len > j - i + 1)) {
                    len = j - i + 1;
                }
            }
        }
        return len;
    }
};

方案二：滑动窗口法
关于滑动窗口这个方法，我们需要注意三个点：

（1）窗口内是什么？
（2）窗口的起始位置是什么，怎么移动？
（3）窗口的结束位置是什么，怎么移动？

如果想清楚这三个点，那么做起题来会更熟练。在这题中，
（1）窗口是满足其和 ≥ target 的长度最小的连续子数组；
（2）窗口的起始位置如何移动：窗口的起始位置设置为数组的起始位置，如果当前窗口的值大于target了，窗口就要向前移动了（也就是该缩小了）；
（3）窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针end。
代码（c++）：

class Solution {
public:
    /**     滑动窗口法 */
    int minSubArrayLen(int target, vector<int>& nums) {
        int start = 0;  //滑动窗口的起始位置
        int len = 0;    //滑动窗口的长度
        int sum = 0;    //滑动窗口数值之和
        int ans = INT_MAX;  //最终结果
        for (int end = 0; end < nums.size(); ++end) {
            sum += nums[end];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while (sum >= target) {
                len = end - start + 1;
                ans = ans < len ? ans : len;
                sum -= nums[start++];   // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
            }
        }
        return ans == INT_MAX ? 0 : ans;
    }
};

不得不说，滑动窗口确实用的妙不可言！而且它的时间复杂度为$O(n)$ 空间复杂度为$O(1)$。【时间复杂度为啥为$O(n)$：不要认为for循环里放一个while就以为是$O(n^2)$， 主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是$O(n)$。】