哪些网站的活动策划做的好,wordpress外观选单分类添加不,沧州网站设计公司,网站建设文件夹结构目录 前言#xff1a;
长度最小的子数组
题目解析
算法原理
算法编写
无重复长度的最小字符串
题目解析
算法原理
算法编写 前言#xff1a;
本文开始#xff0c;介绍的是滑动窗口算法类型的题目#xff0c;滑动窗口本质上其实也是双指针#xff0c;但是呢#…目录 前言
长度最小的子数组
题目解析
算法原理
算法编写
无重复长度的最小字符串
题目解析
算法原理
算法编写 前言
本文开始介绍的是滑动窗口算法类型的题目滑动窗口本质上其实也是双指针但是呢前文介绍的双指针是二者相向移动的 滑动窗口就是同向移动的 本文通过2个题目介绍滑动窗口的基本使用介绍的题目分别是
209. 长度最小的子数组 - 力扣LeetCode
3. 无重复字符的最长子串 - 力扣LeetCode
通过三个步骤介绍第一步是题目解析第二步是算法原理第三步是算法编写同样的会在题目解析部分看是否存在暴力解法那么话不多说进入第一道题目。 长度最小的子数组
题目解析 题目的要求是找到一段连续的区间使得该区间的值的总和大于等于target如果有这种类型的区间返回值应该是这些区间的最小长度。如果没有这种子数组返回的应该为0。
然后是两个示例。那么对于这道题我们可不可以暴力解法呢当然是可以的。
我们只需要找到所有满足该条件的区间并判断他们的长度即可但是时间复杂度的话O(N^2)是肯定的了并且在这道题目上是会超时的所以有兴趣的同学们可以自行尝试。
那么为什么该题目一看就可以使用滑动窗口呢
因为要求的是一段连续的空间作为经验碰到要求是连续空间的题目我们不妨往滑动窗口上靠一下。
现在就进入算法原理部分。
算法原理
滑动窗口的本质是两个指针同向移动我们通过这两个指针的移动判断区间之和是否满足如果满足就进行比较长度大小。
那么如果使用滑动窗口呢 最开始两个指针的起点应该是一样的如果两个指针的位置不是一样的就会导致我们需要多加一个循环来专门求这个区间的和所以现在
int left 0, right 0;
这是肯定的那么滑动窗口我们可以记住两个名词一个是进窗口一个是出窗口什么时候进窗口什么是出窗口是我们题目所关心的。
进窗口代表区间之和target所以需要更多的数参与进来这也是为什么我们不需要排序的原理题目本身要求的是正整数所以我们只需要保证数字越多即可。
出窗口代表区间之和target出窗口判断里面存在的最小长度即可。
基本的原理就是如此一进一出之间可以将题目解决成功。
算法编写
class Solution
{
public:int minSubArrayLen(int target, vectorint nums) {int ans INT_MAX, left 0, right 0 ,sum 0;for(;right nums.size();right){sum nums[right];while(sum target) {ans min(ans,right - left 1);//如果ans为0 那么这一步永远都是0sum - nums[left];}}return ans INT_MAX ? 0 : ans;}
};
但是这道题目有个恶心的点在于如果最开始的长度不定义为很大的一个数判断比较的时候通过min是得不到最小的数的所以我们应该将ans定义为INT_MAX只要是很大的数就可以。
至此题目就解析完毕了。 无重复长度的最小字符串
题目解析 题目非常简短通过条件就是返回不含重复字符的最长字串的长度那么对于字符来说题目中给的要求是 所以我们为了判断有没有重复我们需要一种方法来判断是否存在某种映射我们在这里不妨使用哈希映射使用数组模仿哈希表那么首当其冲的我们不妨判断一下该题目是否存在暴力解法。
那肯定是存在的我们使用两个for循环第二个循环找最末尾的元素同时判断映射值是否大于1大于1直接返回即可。时间复杂度肯定是O(N^2)是可以通过的。
但是鉴于这道题的本质是一段区间所以我们不妨使用滑动窗口解答。
算法原理
上一道题目的滑动窗口是长度最小的子数组判断条件是大于等于target这道题的判断条件是hash映射是否大于1所以得出一个结论是使用滑动窗口的题目有三部曲第一是进窗口第二是判断第三是出窗口。
后面的题目都是很死板的使用该步骤。
那么我们判断的方法同样是使用哈希映射判断映射如果大于1就出出完了记录对应的ans或者是映射满足条件也记录对应的ans即可。
最后返回ans就行。
算法编写
class Solution
{
public:int lengthOfLongestSubstring(string s) {int hash[256] { 0 }, ans 0;for(int left 0, right 0;right s.size();right){hash[s[right]];while(hash[s[right]] 1){hash[s[left]]--;}ans max(ans,right - left 1);}return ans;}
};
滑动窗口的开篇就结束咯~ 感谢阅读
