本内容是笔者结合《代码随想录》总结所得,记录学习过程,分享知识!
目录:
1. 开篇例题:209. 长度最小的子数组
2. 题解参考- - 2.1 方法一:暴力法
- - 2.2 方法二:滑动窗口3. 方法思路点拨:滑动窗口
- - 3.1 直白解释
- - 3.2 本题思路点拨4. 相关题集
1. 开篇例题:209. 长度最小的子数组
例题:点击直飞
2. 题解参考
2.1 方法一:暴力法
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
// 双循环暴力法
int sum = 0;
int res = INT32_MAX;
int len = 0;
for(int i = 0;i<nums.size();i++){ // 设置子数组起始点
sum = 0;
for(int j = i;j<nums.size();j++){ // 探索子数组终点
sum += nums[j];
if(sum >= target){
len = j-i+1; // 子列长度
res = res > len?len:res;
break;
}
}
}
return res == INT32_MAX? 0:res;
}
};
2.2 方法二:滑动窗口
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
// 滑动窗口
int res = INT32_MAX;
int len = 0; // 子数列长度
int i =0; // 子列起始位
int sum = 0;
for(int j = 0; j<nums.size() ;j++){
sum += nums[j];
while(sum >= target){ // 核心代码
len = j-i+1; // 获取合法子数列长度
res = res > len ? len : res;
sum -= nums[i++];
// 子列起始位长度调整,改写法规避了可能单次移动遇到负数引起的重复操作!
}
}
return res == INT32_MAX?0:res;
}
};
3. 方法思路点拨:滑动窗口
3.1 双指针算法应用:滑动窗口
滑动窗口的思路即:使用两个指针维护一个区间【通常是左闭右闭区间】,这区间具有可变性,类似与二分法中的边界重定向,使得区间减小。
但此处的滑动窗口显然高级:可变大、可变小!【窗口大小依据问题情景而定】(如下图)
3.2 本题思路点拨
依据题设,我们需要找到一个区间,该区间内的元素之和满足不小于指定值。同时需要满足:找到的区间是最小的。
此题即可使用滑动窗口去探索最小区间!文章来源:https://www.toymoban.com/news/detail-442205.html
4. 相关题集
待选中文章来源地址https://www.toymoban.com/news/detail-442205.html
到了这里,关于算法刷题营【Day2】:: 双指针算法应用:滑动窗口 :209. 长度最小的子数组的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!