209. 长度最小的子数组

思路一：暴力解法

通过两个for循环，从头开始找符合条件的子序列。暴力解法无法通过本题，超出时间限制，所以仅供参考。

代码如下：

暴力解法1：下面的代码是通过申请一个新的数组，将满足条件的子序列的长度放到新数组里面，然后再对数组排序返回最小的元素。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        vector<int> v; //通过新申请一个数组
        for (int i = 0; i < nums.size(); i++)
        {
            int sum = 0;//元素之和
            int count = 0; //子序列长度
            for (int j = i; j < nums.size(); j++)
            {
                sum += nums[j];
                count++;
                if (sum >= target) //是否满足条件，满足条件将子序列长度放进新数组
                {
                    v.push_back(count);
                    break;
                } 
            }
        }
        if(v.size() == 0) //当新数组中没有元素时即没有一个符合条件的返回0
            return 0;
        sort(v.begin(), v.end()); //对新数组排序
        return v[0];//返回最小的
    }
};

时间复杂度：O(N^2^ + N*logN)

空间复杂度：O(N)

暴力解法2：通过设置几个变量记录。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sum = 0;//子序列之和
        int sublength = 0; //子序列长度
        int result = INT32_MAX;//最后的长度,初始化时设置最大值方便后续比较
        for(int i = 0; i < nums.size(); i++)
        {
            sum = 0;
            sublength = 0;
            for(int j = i; j < nums.size(); j++)
            {
                sum += nums[j];
                sublength++;
                if(sum >= target)
                {
                	//sublength = j - i + 1;//也可以通过这种方式计算
                    result = result < sublength ? result:sublength;
                }
            }
        } 
        return result == INT32_MAX ? 0 : result;
    }
};

时间复杂度：O(N^2^)

空间复杂度：O(1)

思路2：滑动窗口法

确定for循环中的j是终止位置，设置一个变量i为起始位置，先计算出满足条件的sum，然后通过while改变起始位置i，不满足while条件的话就会进入for循环改变终止位置j，从而做到滑动。根据题目给出的测试用例，具体分析如下图：

代码如下：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int sum = 0;//子序列之和
        int sublength = 0; //子序列长度
        int result = INT32_MAX;
        int i = 0;//滑动窗口起始位置
        for(int j = 0; j < nums.size(); j++)
        {
            sum += nums[j];
            while(sum >= target)
            {
                sublength = j - i + 1;//计算出当满足条件时的长度
                result = sublength > result ? result:sublength;//找出值相对较小的那个
                sum -= nums[i++];//改变起始位置
            }
        }
        return result == INT32_MAX ? 0:result; //当result的值没改变时，返回0
    }
};