初识算法 · 滑动窗口(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 那么这一步永远都是0
sum -= 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;
}
};滑动窗口的开篇就结束咯~
感谢阅读！