Leetcode209

长度最小的子数组

Leetcode209

题目描述

给定一个含有 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

思路

暴力法

首先利用vector的求和函数，判断所有元素之和是否小于target，是直接返回0，否则进入else。
else部分则是利用两层循环，求出所有该数组的子序列，对每个子序列求和，每次计算符合条件的子序列长度，若比已求出最小子序列长度小，则更新子序列长度。从下标0开始求0-1，0-2，…，0-（len-1）的子序列，当已求得0-r的满足条件的序列时，可以直接跳出内循环，不再求0-r+1的序列，无意义。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        if(accumulate(nums.begin(),nums.end(),0)<target)
            return 0;
        else{
            int temp =  0;  //当前子序列长度
            int sums = 0;    //子序列和
            int len = INT32_MAX; //最终子序列长度       
            for(int i =0;i<nums.size();i++){
                sums = 0;
                for(int j=i;j<nums.size();j++){
                    sums += nums[j];
                    if(sums>=target){
                        temp = j - i +1;
                        len = len < temp ? len : temp;
                        break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
                    }
                }
            }
            return len;
        }
    
    }
};

滑动窗口法

该方法主要也是双指针法，开始时都指向0，头指针不移动，尾指针移动，直到尾指针头指针指向所形成的区间内的数之和满足要求时，区间收缩，减去头指针所指向的数，头指针移动，头指针移动的条件时：保证区间内的数之和满足条件。

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while (sum >= s) {
                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)$

参考

代码随想录