西安市城市建设档案馆官方网站,网站服务器租用恒创,fusionaccess免费服务器,域名备案的网站建设方案书模板文章目录 算法原理题目解析暴力枚举法的代码优化第一步初始化第二步right右移第三步left右移 滑动窗口法的代码 算法原理 滑动窗口是一种在序列#xff08;例如数组或链表#xff09;上解决问题的算法模式。它通常用于解决子数组或子字符串的问题#xff0c;其中滑动窗口表示… 文章目录 算法原理题目解析暴力枚举法的代码优化第一步初始化第二步right右移第三步left右移 滑动窗口法的代码 算法原理 滑动窗口是一种在序列例如数组或链表上解决问题的算法模式。它通常用于解决子数组或子字符串的问题其中滑动窗口表示一个范围这个范围在序列上移动以便找到满足特定条件的子数组或子字符串。 算法的基本思想是维护两个指针通常是左右两个指针表示滑动窗口的左右边界。通过调整这两个指针可以滑动窗口在序列上移动。在每个窗口位置都可以根据问题的要求进行处理比如计算窗口内的和、最大值、最小值或者检测满足某些条件的子数组或子字符串等。 滑动窗口算法的一般步骤如下 初始化左右指针 将左指针和右指针初始化为序列的起始位置。 滑动窗口 移动右指针以扩大窗口或移动左指针以缩小窗口直到满足问题的条件。 处理窗口数据 在每个窗口位置根据问题的要求处理窗口内的数据比如计算窗口内的和、最大值、最小值或者检测满足某些条件的子数组或子字符串。 更新结果 根据问题的要求更新结果。 重复 重复2-4步骤直到右指针到达序列的末尾。 滑动窗口算法通常能够在线性时间内解决一些与子数组或子字符串相关的问题因为每个元素至多被访问两次一次由左指针一次由右指针。这种算法的时间复杂度通常是 O(N)其中 N 是序列的长度。 实际应用中滑动窗口算法可以解决一系列问题如最大子数组和、最小覆盖子串、最长无重复字符子串等。 题目解析
废话不多说先上题目链接leetcode—长度最小子数组 那么接下来我们一起解析一下例题如下图 首先最重要的肯定是读懂题目题目意思其实也很容易读懂意思就是给我们一个数字target和一个数组要求在这个数组中找到一个必须是连续的子数组并且这个子数组每个元素加起来target并从找到的这些数组中取一个最短的数组那么炸一看可能会感觉有些茫然但是学习算法我们要记住一个步骤就是面对一个题目的时候先想一下如何暴力的把他求出来那么很简单那就是找到所有的子数组并从这些子数组中找到和target的数组之后取得最小值那么我们把暴力的方法先写出来代码如下
暴力枚举法的代码
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int ans0x9f9f9f;for(int i0;inums.size();i){int t0;for(int ji;jnums.size();j){tnums[j];if(ij){if(ttarget){ansmin(ans,j-i1);break;}}if(ttarget){ansmin(ans,j-i1);break;}}}if(ans0x9f9f9f){return 0;}return ans;}
};由于力扣的后台测试数据比较小所以这个暴力的解法也可以过但是我们可以清楚的看到这个算法的时间复杂度达到了O(n^2)因此这个时间负责度还是比较高的因此我们有没有更简单的办法呢
优化
使用滑动窗口进行优化 在这道题目中我们可以看到两个重要信息 1、子数组必须是连续的 2、子数组的和需要target 那么我们可以想一下我们可以使用两个指针一个是left一个是right当left和right之间的元素和小于target的时候就让right一直向右移动当right和left之间的元素大于等于target的时候我们更新一下此时的长度是否为最短然后再让left左移查看此时right和left的元素之和是否大于等于target如果是就继续上一步操作即继续更新我们的最短长度一直到right和left之间的数据小于target为止之后再让right指针右移即可。 我给大家举出一个例子说明一下。
第一步初始化 第二步right右移 此时我们可以发现right和left之间的元素和超过了target因此我们与目标值进行比较取得较小的那个然后让left右移之后再进行查看此时right和left之间的元素和是否大于等于target。
第三步left右移 此时我们右移后发现right和left之间的元素和小于target因此right继续右移然后后续一直重复这个操作即可
滑动窗口法的代码
class Solution {
public:int minSubArrayLen(int target, vectorint nums) {int left0;int right0;int sumnums[0];int ansmin100010;while(rightnums.size()leftnums.size()){if(sumtarget){ansminmin(right-left1,ansmin);sum-nums[left];left;}else{right;if(rightnums.size())sumnums[right];else break;}}if(ansmin100010){return 0;}return ansmin;}
};我们可以从用时分布图清楚的看到我们的时间效率有了很大的提升。
