初识算法 · 滑动窗口(1)

目录

 前言：

长度最小的子数组

题目解析

算法原理

算法编写

无重复长度的最小字符串

题目解析

算法原理

算法编写

---

 前言：

本文开始，介绍的是滑动窗口算法类型的题目，滑动窗口本质上其实也是双指针，但是呢，前文介绍的双指针是二者相向移动的：

滑动窗口就是同向移动的：

本文通过2个题目，介绍滑动窗口的基本使用，介绍的题目分别是：

209. 长度最小的子数组 - 力扣（LeetCode）

3. 无重复字符的最长子串 - 力扣（LeetCode）

通过三个步骤介绍，第一步是题目解析，第二步是算法原理，第三步是算法编写，同样的，会在题目解析部分看是否存在暴力解法，那么话不多说，进入第一道题目。

---

长度最小的子数组

题目解析

题目的要求是，找到一段连续的区间，使得该区间的值的总和大于等于target，如果有这种类型的区间，返回值应该是这些区间的最小长度。如果没有这种子数组，返回的应该为0。

然后是两个示例。那么对于这道题我们可不可以暴力解法呢？当然是可以的。

我们只需要找到所有满足该条件的区间，并判断他们的长度即可，但是时间复杂度的话，O(N^2)是肯定的了，并且在这道题目上是会超时的，所以有兴趣的同学们可以自行尝试。

那么为什么该题目一看就可以使用滑动窗口呢？

因为要求的是一段连续的空间，作为经验，碰到要求是连续空间的题目，我们不妨往滑动窗口上靠一下。

现在就进入算法原理部分。

算法原理

滑动窗口的本质是，两个指针同向移动，我们通过这两个指针的移动，判断区间之和是否满足，如果满足就进行比较长度大小。

那么如果使用滑动窗口呢？
最开始两个指针的起点应该是一样的，如果两个指针的位置不是一样的，就会导致我们需要多加一个循环来专门求这个区间的和，所以现在：

int left = 0, right = 0;

这是肯定的，那么滑动窗口，我们可以记住两个名词，一个是进窗口，一个是出窗口，什么时候进窗口，什么是出窗口，是我们题目所关心的。

进窗口代表，区间之和<target，所以需要更多的数参与进来，这也是为什么我们不需要排序的原理，题目本身要求的是正整数，所以我们只需要保证数字越多即可。

出窗口代表，区间之和>target，出窗口判断里面存在的最小长度即可。

基本的原理就是如此，一进一出之间，可以将题目解决成功。

算法编写

class Solution 
{
public:int minSubArrayLen(int target, vector<int>& 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;}
};

滑动窗口的开篇就结束咯~

---

感谢阅读！