Leetcode题解:209长度最小的子数组,掌握滑动窗口从此开始!!!
一、题目内容
题目要求找出给定数组中满足总和大于等于目标值 target 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
二、题目分析
1. 输入和输出
输入：
一个正整数数组
nums，表示给定的数组。一个正整数
target，表示目标值。
输出：
一个整数，表示满足总和大于等于
target的长度最小的连续子数组的长度。如果不存在符合条件的子数组，则返回 0。
2. 算法逻辑
使用滑动窗口算法来解决这个问题。
初始化两个指针
left和right，分别表示窗口的左右边界，初始值均为 0。初始化一个变量
sum，用于存储当前窗口内的元素和，初始值为 0。初始化一个变量
min_length，用于存储满足条件的最短子数组的长度，初始值为正无穷大（INT_MAX）。遍历数组：
将
right指针所指向的元素值加入sum。如果
sum大于等于target，则尝试通过移动left指针来缩小窗口，同时更新min_length。移动
right指针，继续扩展窗口。
遍历结束后，如果
min_length仍为正无穷大，说明没有找到符合条件的子数组，返回 0；否则返回min_length。
三、解题要点
1. 滑动窗口的定义
滑动窗口是一种用于解决数组或字符串问题的有效算法，特别适用于处理涉及连续子数组（串）的问题。在本题中，滑动窗口用于动态调整子数组的范围，以找到满足条件的最短子数组。
2. 窗口的移动
右指针移动：右指针不断向右移动，将新元素加入窗口，累加窗口内的和。
窗口收缩：当窗口内的和大于等于
target时，尝试通过移动左指针来缩小窗口，同时更新最小长度。
3. 算法复杂度
时间复杂度：O(n)，其中 n 是数组的长度。每个元素最多被访问两次（一次由右指针，一次由左指针）。
空间复杂度：O(1)，只需要常数级别的额外空间。
四、代码解答
以下是使用滑动窗口算法的 C++ 实现代码：
#include <vector>
#include <algorithm>
#include <climits>class Solution {
public:int minSubArrayLen(int target, std::vector<int>& nums) {int n = nums.size();int left = 0, right = 0;int sum = 0;int min_length = INT_MAX;while (right < n) {sum += nums[right]; // 将右指针的值加入窗口while (sum >= target) { // 如果窗口内的和大于等于目标值min_length = std::min(min_length, right - left + 1); // 更新最小长度sum -= nums[left]; // 移动左指针，缩小窗口left++;}right++;}return (min_length == INT_MAX) ? 0 : min_length; // 如果没有找到满足条件的子数组，返回0}
};以下是c语言实现代码:
int minSubArrayLen(int target, int* nums, int numsSize) {// 初始化变量int len = 0; // 用于记录当前满足条件的子数组长度int sum = 0; // 当前窗口内的元素和int left = 0; // 左指针，表示窗口的左边界int min_len = numsSize + 1; // 用于记录最小长度，初始值设为数组长度加1（一个不可能达到的值）// 遍历数组，右指针从0到numsSize-1for (int i = 0; i < numsSize; i++) {// 将右指针所指向的元素值加入窗口和sum += nums[i];// 当窗口内的和大于等于目标值时，尝试收缩窗口while (sum >= target) {// 计算当前窗口的长度len = i - left + 1;// 如果当前窗口长度小于已记录的最小长度，则更新最小长度if (len < min_len) {min_len = len;}// 移动左指针，缩小窗口，并从窗口和中减去左指针所指向的元素值sum -= nums[left];left++;}}// 如果min_len仍大于numsSize，说明没有找到满足条件的子数组，返回0// 否则返回找到的最小长度return (min_len > numsSize) ? 0 : min_len;
}五、详细注释
1. 滑动窗口算法
窗口扩展：右指针向右移动，将新元素加入窗口，累加窗口内的和。
窗口收缩：当窗口内的和大于等于
target时，尝试通过移动左指针来缩小窗口，同时更新最小长度。
2. 终止条件
当右指针遍历完整个数组时，结束循环。
3. 返回值
如果没有找到满足条件的子数组，返回 0。
否则返回找到的最短子数组的长度。
六、代码执行过程示例
假设我们有一个数组 nums = [2, 3, 1, 2, 4, 3] 和目标值 target = 7。
代码执行过程
初始状态：
left = 0,right = 0,sum = 0,min_length = INT_MAX
右指针移动：
right = 0,sum = 2right = 1,sum = 5right = 2,sum = 6right = 3,sum = 8（满足条件）
左指针移动：
left = 0,sum = 8,min_length = 4left = 1,sum = 6,min_length = 4left = 2,sum = 5,min_length = 4left = 3,sum = 4,min_length = 4
右指针继续移动：
right = 4,sum = 8（满足条件）left = 3,sum = 8,min_length = 3left = 4,sum = 4,min_length = 3
右指针继续移动：
right = 5,sum = 7（满足条件）left = 4,sum = 7,min_length = 2left = 5,sum = 3,min_length = 2
结束：
right = 6，结束循环返回
min_length = 2
最终结果
最终返回的最小长度为 2，对应的子数组为 [4, 3]。
