python 做网站优势,拨打12355可以找团员密码吗,福州网站制作设计,网站 无限下拉目录 0.滑动窗口原理讲解1.长度最小的子数组1.题目链接2.算法原理讲解3.代码实现 0.滑动窗口原理讲解
滑动窗口#xff1a;“同向双指针”滑动窗口可处理「⼀段连续的区间」问题如何使用#xff1f; left 0, right 0进窗口判断 是否出窗口 更新结果 - 视情况而定 可能… 目录 0.滑动窗口原理讲解1.长度最小的子数组1.题目链接2.算法原理讲解3.代码实现 0.滑动窗口原理讲解
滑动窗口“同向双指针”滑动窗口可处理「⼀段连续的区间」问题如何使用 left 0, right 0进窗口判断 是否出窗口 更新结果 - 视情况而定 可能在出窗口前可能在进窗口之后 具体原理解析将结合**「长度最小的子数组」**来说明 1.长度最小的子数组
1.题目链接
长度最小的子数组 2.算法原理讲解 此问题分析的对象是**「⼀段连续的区间」因此可以考虑「滑动窗⼝」**的思想来解决 让滑动窗⼝满⾜ 从i位置开始窗⼝内所有元素的和⼩于target当窗⼝内元素之和第⼀次⼤于等于⽬标值的时候就是i位置开始满⾜条件的最⼩⻓度 做法 如果窗⼝sum target 更新结果并且将左端元素划出去的同时继续判断是否满⾜条件并更新结果 因为左端元素可能很⼩划出去之后依旧满⾜条件 如果窗⼝sum不满⾜条件 right让下⼀个元素进⼊窗⼝ 为何滑动窗⼝可以解决问题并且时间复杂度更低 这个窗⼝寻找的是以当前窗⼝最左侧元素(记为left1)为基准符合条件的情况 即从left1开始满⾜sum target时的最右侧(记为right1)能到哪⾥ 既然已经找到从left1开始的最优的区间那么就可以⼤胆舍去left1 但是如果继续像暴力求解⽅法⼀样重新开始统计第⼆个元素(left2)往后的和势必会有⼤量重复的计算 因为在求第⼀段区间的时候已经算出很多元素的和了这些和是可以在计算下次区间和的时候⽤上的 此时rigth1的作⽤就体现出来了只需将left1这个值从sum中剔除 从right1这个元素开始往后找满⾜left2元素的区间 此时right1也有可能是满⾜的因为left1可能很⼩sum剔除掉left1之后依旧满⾜⼤于等于 target 这样就能省掉⼤量重复的计算总结利用单调性规避了很多没有必要的枚举行为 此处的单调指滑动窗口内sum的单调性而不是数组原始数据的单调性 时间复杂度 O ( N ) O(N) O(N) 虽然代码是两层循环但是left指针和right指针都是不回退的两者最多都往后移动n次 3.代码实现
int MinSubArrayLen(int target, vectorint nums)
{int sum 0, len INT_MAX;for(int left 0, right 0; right nums.size(); right){sum nums[right]; // 进窗口while(sum target) // 判断{len min(len, right - left 1); // 更新结果sum - nums[left]; // 出窗口}}return len INT_MAX ? 0 : len;
}
