帮别人做网站市场价,北京哪家做网站和网络推广好的,企业门户网站建设情况汇报,安卓应用开发用什么语言滑动窗口算法:
今天我们来学习一个新的算法.滑动窗口解法,但是我们不直接说明此解法,而是先使用暴力解法,再引入滑动窗口来优化,这样才能解决此类问题.
网页直达:
https://leetcode.cn/problems/2VG8Kg 题目解析:
1.数组的数字均为正整数.
2.满足条件(sumtarget)的子数…滑动窗口算法:
今天我们来学习一个新的算法.滑动窗口解法,但是我们不直接说明此解法,而是先使用暴力解法,再引入滑动窗口来优化,这样才能解决此类问题.
网页直达:
https://leetcode.cn/problems/2VG8Kg 题目解析:
1.数组的数字均为正整数.
2.满足条件(sumtarget)的子数组是连续的.
一.暴力解法:
枚举所有连续的子数组的和O(N^3)
优化:我们知道数组里面都是正整数.那我们的left,right遍历时.我们就要求sum,但是求sum遍历时一定是单调递增的,在满足第一个sumtarget,求和时遍历的指针就不回退求和,利用单调性,减少了很多没有必要的枚举行为.
二.滑动窗口算法:
怎么用滑动窗口算法呢?
1.left0;right0;
2.进窗口
3.判断(这里就是判断完之后就更新minlen)
4.出窗口
5.什么时候更新结果呢?就题目而论
同样的,我们还是要勤画图来了解其中的过程 代码实现:
无注释:
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int right0,left0;int sum0;int minlenINT_MAX;int nnums.size();for(int right0;rightn;right){sumnums[right];while(sumtarget){int curlenright-left1;if(minlencurlen){minlencurlen;}sum - nums[left]; // 移除左元素否则sum不会减小left;}}return minlenINT_MAX?0:minlen;}
};
详解,注释:
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int right0,left0;//左右指针int sum0;int minlenINT_MAX;int nnums.size();for(int right0;rightn;right)//右元素遍历{sumnums[right];//增加右元素,相当于扩大窗口while(sumtarget){int curlenright-left1;//计算长度if(minlencurlen)//更新最小长度{minlencurlen;}sum - nums[left]; // 移除左元素否则sum不会减小left;//左元素遍历}}return minlenINT_MAX?0:minlen;//存不存在不满足target的情况}
};
