一.题目习题链接209. 长度最小的子数组 - 力扣LeetCode二.题目讲解给定全正整数数组nums和正整数target找到连续子数组满足子数组和 ≥ target 要求找出满足条件的最短子数组长度不存在返回 0。⚠️关键点子数组 连续元素数组所有元素都是正数这是算法优化的核心前提三.算法原理讲解解法一暴力枚举首先我们想到的肯定是遍历所有子数组然后找到一个一个匹对找到最小的那个子数组长度。枚举所有子数组起点 i再从起点向后不断累加元素终点 j一旦区间和 ≥ target记录区间长度j-i1因为往后 j 更大长度只会更长内层循环可以直接 break。缺点时间复杂度 O(n^2)暴力会超时只能用来理解题意不能 AC。解法二利用单调性“同向双指针”来优化我们不是在讲滑动窗口怎么用双指针来解题了呢这里的双指针不是我们之前提到的双指针这里我们来分析一下1.单调性由于数组中存放的全是正整数所以每次加一个数都会变大单调递增的2.同向双指针两个指针朝同一个方向运动下面我们画图来分析定义两个指针开始时指向0然后让右指针不断向后面走将 [left , right]之间的区间看作一个窗口right向后面走的时候就相当于数据进窗口然后不断sum直到sumtarget停下来这时找到一个区间长度注意right后面的数就不用进窗口了因为进去之后的长度都要比现在的长我们找的是最小的那个区间长度这里就用到了单调性然后是让left就相当去出窗口right是重新指向left还是不动呢这里我们可以通过运动观察到如果指向图一走之后还会变到图二这种状态所以不需要让right指针回到left的位置这也是滑动窗口的由来同时这里也是前面讲的同向双指针这里注意出窗口前要更新len的长度然后让sum-left后继续判断sum和target的关系重复该操作结束条件right走向末尾四.编写代码这里需要注意几个点1.外层循环是让right一直向后面走直到走到末尾才结束内层循环是让left直到sumtarget才结束2.绿色框因为更新长度要取最小的这里如果给0就会一直是0所以给最大3.红色框是判断条件为什么是等号因为是循环是先判断再更新长度最后才会出窗口所以当sumtarget的时候还要更新长度然后后面sum会小于target但是他不会进入循环len也就不会变4.蓝色框这里是判断len长度是否变化变化了说明进入了循环说明sumtarget返回len没变化说明没有进入循环sumtarget没有满足条件的子数组然后就返回0class Solution { public: int minSubArrayLen(int target, vectorint nums) { int left 0, sum 0,len INT_MAX; for(int right 0; right nums.size();right) { sum nums[right]; // 进窗口 while(sum target) { //更新长度 len min(len,right - left 1); sum - nums[left]; left; } } return len INT_MAX ? 0 : len; } };
一.题目习题链接209. 长度最小的子数组 - 力扣LeetCode二.题目讲解给定全正整数数组nums和正整数target找到连续子数组满足子数组和 ≥ target 要求找出满足条件的最短子数组长度不存在返回 0。⚠️关键点子数组 连续元素数组所有元素都是正数这是算法优化的核心前提三.算法原理讲解解法一暴力枚举首先我们想到的肯定是遍历所有子数组然后找到一个一个匹对找到最小的那个子数组长度。枚举所有子数组起点 i再从起点向后不断累加元素终点 j一旦区间和 ≥ target记录区间长度j-i1因为往后 j 更大长度只会更长内层循环可以直接 break。缺点时间复杂度 O(n^2)暴力会超时只能用来理解题意不能 AC。解法二利用单调性“同向双指针”来优化我们不是在讲滑动窗口怎么用双指针来解题了呢这里的双指针不是我们之前提到的双指针这里我们来分析一下1.单调性由于数组中存放的全是正整数所以每次加一个数都会变大单调递增的2.同向双指针两个指针朝同一个方向运动下面我们画图来分析定义两个指针开始时指向0然后让右指针不断向后面走将 [left , right]之间的区间看作一个窗口right向后面走的时候就相当于数据进窗口然后不断sum直到sumtarget停下来这时找到一个区间长度注意right后面的数就不用进窗口了因为进去之后的长度都要比现在的长我们找的是最小的那个区间长度这里就用到了单调性然后是让left就相当去出窗口right是重新指向left还是不动呢这里我们可以通过运动观察到如果指向图一走之后还会变到图二这种状态所以不需要让right指针回到left的位置这也是滑动窗口的由来同时这里也是前面讲的同向双指针这里注意出窗口前要更新len的长度然后让sum-left后继续判断sum和target的关系重复该操作结束条件right走向末尾四.编写代码这里需要注意几个点1.外层循环是让right一直向后面走直到走到末尾才结束内层循环是让left直到sumtarget才结束2.绿色框因为更新长度要取最小的这里如果给0就会一直是0所以给最大3.红色框是判断条件为什么是等号因为是循环是先判断再更新长度最后才会出窗口所以当sumtarget的时候还要更新长度然后后面sum会小于target但是他不会进入循环len也就不会变4.蓝色框这里是判断len长度是否变化变化了说明进入了循环说明sumtarget返回len没变化说明没有进入循环sumtarget没有满足条件的子数组然后就返回0class Solution { public: int minSubArrayLen(int target, vectorint nums) { int left 0, sum 0,len INT_MAX; for(int right 0; right nums.size();right) { sum nums[right]; // 进窗口 while(sum target) { //更新长度 len min(len,right - left 1); sum - nums[left]; left; } } return len INT_MAX ? 0 : len; } };
