209.长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。

示例:

输入:s = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。

滑动窗口法:

1.我们在字符串 S 中使用双指针中的左右指针技巧,初始化 left = right = 0,把索引闭区间 [left, right] 称为一个「窗口」。

2.我们先不断地增加 right 指针扩大窗口 [left, right],直到窗口中的字符串符合要求(包含了 T 中的所有字符)。

3.此时,我们停止增加 right,转而不断增加 left 指针缩小窗口 [left, right],直到窗口中的字符串不再符合要求(不包含 T 中的所有字符了)。同时,每次增加 left,我们都要更新一轮结果。

4.重复第 2 和第 3 步,直到 right 到达字符串 S 的尽头。

这个思路其实也不难,第 2 步相当于在寻找一个「可行解」,然后第 3 步在优化这个「可行解」,最终找到最优解。左右指针轮流前进,窗口大小增增减减,窗口不断向右滑动。

    int minSubArrayLen(int s, vector<int>& nums) {
        int minLen=0;
        int left=0,right=0,sum=0;
        while(right<nums.size()){
            sum+=nums[right];
            while(sum>=s){
                minLen=(minLen==0?right-left+1:min(minLen,right-left+1));
                sum-=nums[left++];
            }
            right++;
        }
        return minLen;
    }
上一篇:滑动窗口之LeetCode209长度最小的子数组


下一篇:2021-03-15