【算法|滑动窗口No.1】leetcode209. 长度最小的子数组

个人主页：兜里有颗棉花糖
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创
收录于专栏【手撕算法系列专栏】【LeetCode】
🍔本专栏旨在提高自己算法能力的同时，记录一下自己的学习过程，希望对大家有所帮助
🍓希望我们一起努力、成长，共同进步。

点击直接跳转到该题目

1️⃣题目描述

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

注意：

• 1 <= target <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

2️⃣算法分析

解题思路如下：

• 步骤一：使用双指针left和right来构建滑动窗口，初始时left和right都为0。
• 步骤二：进入循环，将右指针right向右移动，每次将nums[right]的值加到sum中。
• 步骤三：进入while循环，判断当前窗口内的和sum是否大于等于目标值target。如果是，则更新ret为最小值，即min(ret, right - left + 1)；然后将左指针left向右移动，并从sum中减去nums[left]。
• 然后循环步骤二和步骤三，直到右指针right达到数组的末尾；最后返回结果即可。

3️⃣代码编写

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int ret = INT_MAX, sum = 0;
        for(int left = 0,right = 0;right < n;right++)
        {
            // 进窗口
            sum += nums[right];

            while(sum >= target)
            {
                // 更新结果
                ret = min(ret,right - left + 1);

                // 出窗口
                sum -= nums[left++];
            }
        }
        return ret == INT_MAX ? 0 : ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

最后就是通过啦！！！