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

点击直接跳转到该题目

1️⃣题目描述

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [nums[l], nums[l+1], ..., nums[r-1], nums[r]] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例1：

示例2：

示例3：

注意：

• 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;
    }
};

最后就是通过啦！！！