算法第七天：leetcode之209.长度最小的子数组

一、长度最小的子数组

    209.长度最小的子数组的链接：https://leetcode.cn/problems/minimum-size-subarray-sum/

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

  提示：

• 1 <= target <= 109
• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105

  进阶：

• 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

  双指针滑动窗口的基础知识如下链接所示，感兴趣的读者可以点击或者复制该链接进行查阅和学习：

 https://mp.csdn.net/mp_blog/creation/editor/139633714

   本题使用滑动窗口的算法知识解题，以下是部分c++代码(省略力扣给出的代码块内容)：

        int sum=0, i=0;
        int l=0;
        int result=INT32_MAX;
        for(int j=0;jsize();j++){
            sum+=nums[j];
            while(sum>=target){
                l=j-i+1;
                result=min(result, l);
                sum=sum-nums[i];
                i++;
            }
        }
        return result==INT32_MAX ? 0 : result;

二、长度最小的子数组的基本思路

1.  定义起始位置i，和终止位置j，然后不断调节子序列的起始位置和终止位置，定义一个最大值result去查找通过不断调节找最小的子数组；
2. 用for循环查找，先求滑动窗口的数值之和，在和目标值target比较；
3. 为什么用while循环？因为要一直循环查找，而且还要判断条件，所以用while循环比较好。取子序列的长度i，然后去找最小的子数组，sum=sum-num[i++]，通过更新i的值，从而去不断变更初始位置i；
4. 最后如果result没有被赋值，则返回0，说明没有符合条件的子序列。如果被赋值，则返回result。

 三、结言

    感谢各位读者的阅读与支持，您的支持是我前进的动力！我希望我的博文能够带给您有用的滑动窗口算法知识和启发。如果您有任何问题或意见，请随时联系我或在评论区评论。希望本题的算法知识对大家有帮助，我会一直持续更新算法知识的博客哦，谢谢各位读者的支持！！！