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

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-size-subarray-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法：滑动窗口（窗口大小不定） 

class Solution {
public:
    /*暴力解法：不推荐，时间复杂度为O(n^2)，力扣上不会通过，超出时间限制
    时间复杂度：O(n^2) 空间复杂度：O(1)*/
    /*
    int minSubArrayLen(int target, vector<int>& nums) {
        int result = INT32_MAX; //最终的结果，长度最短的连续子数组
        int subLength = 0;      //当前遍历到的子序列的数值之和
        int size = nums.size();
        for(int i = 0; i < size; ++i) {  //设置子序列int sum = 0;
            for(int j = i; j < size; ++j) { //设置子序列终点为j
                sum += nums[j];
                if(sum >= target) {  //一旦满足条件就更新result的大小
                    subLength = j - i + 1;
                    result  = result < subLength ? result : subLength;
                    break; //已经找到了当前最短的子序列，所以直接break
                }
            }
        }
        //如果result没有被赋值，说明没有满足条件的连续子序列，返回0
        return result == INT32_MAX ? 0 : result; 
    }
    */
    
    /*推荐解法：滑动窗口*/
    int minSubArrayLen(int target, vector<int>& nums) {
        int result = INT32_MAX;  //返回的结果，初始先设为最大值，后面不断的更新它
        int subLength = 0;       //当前遍历到的满足返回条件的连续子序列的长度，滑动窗口的长度
        int size = nums.size();  //给定的数组的大小
        int i = 0;               //滑动窗口的起始位置
        int sum = 0;             //当前遍历到的序列的加和，滑动窗口数值之和
        for(int j = 0; j < size; ++j) {
            sum += nums[j];
            //这里一定要使用while不能使用if,每次更新i(起始位置)，要不断比较子序列是否符合条件
            while(sum >= target) {
                subLength = j - i + 1; //取子序列的长度
                result = result < subLength ? result : subLength;
                sum -= nums[i++]; //滑动窗口的精髓，不断地变更i起始位置
            }
        }
        //如果result没有被赋值，说明没有满足条件的连续子序列，返回0
        return result == INT32_MAX ? 0 : result;
        //时间复杂度：O(n) 空间复杂度：O(1)
    }
};