初识算法 · 滑动窗(1)

目录。

 前言：

子数组长度最小。

题目解析。

算法原理。

算法编写。

无重复长度的最小字符串。

题目解析。

算法原理。

算法编写。

 前言：

本文开始�介绍了滑动窗算法类型的主题，本质上，滑动窗也是双指针，但是，前面介绍的双指针是相对移动的：

滑动窗是同向移动的：

本文通过两个主题󿀌介绍滑动窗的基本使用，主题分别是：

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

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

三步介绍󿀌第一步是题目分析，第二步是算法原理，第三步是编写算法，同样的，问题分析部分会有暴力解决方案，所以不要说太多󿀌进入第一个题目。

子数组长度最小。

子数组长度最小。

题目分析。

主题的要求是，找到连续的范围，该区间的总值大于等于target，如果有这种范围，返回值应该是这些范围的最小长度。如果没有这样的子数组󿀌返回的应该是0。

然后是两个例子。所以我们能暴力解决这个问题吗？当然可以。

我们只需要找到所有符合这一条件的范围，并判断它们的长度，但如果时间复杂，，O(N^2)是肯定的，而且这个话题会超时，所以感兴趣的同学可以自己试试。

那为什么这个题目一眼就能用滑动窗口࿱呢？f;因为需要一个连续的空间。

，作为经验�要求是连续空间的话题，我们不妨靠在滑动窗上。

现在进入算法原理部分。

算法原理。

滑动窗的本质是，两个指针同向移动，通过这两个指针的移动，判断区间之和是否符合#xff0c;比较长度大小，如果满意。
那么如果使用滑动窗？

前两个指针的起点应该是一样的，如果两个指针的位置不一样，这将导致我们需要增加一个循环来寻求这个范围和，现在：

int left = 0, right = 0;

这是肯定的，然后滑动窗󿀌我们能记住两个名词，一个是进窗，一个是出口窗口，何时进入窗口࿰？c;什么是窗口࿰？c;这是我们的话题所关心的。窗口代表。

，区间之和<target，因此，需要更多的数字参与，这就是为什么我们不需要排序的原理，主题本身需要正整数，所以我们只需要确保数字越多。窗口代表。

，区间之和>target，判断出窗口中存在的最小长度。

这是࿰的基本原理c;一进一出之间，能成功解决问题。

算法编写。

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获得c;所以我们应该把ans定义为INT__MAX，只要是一个大数字就可以了。 0 : ans; }};

但这个话题的恶心之处在于，如果最初的长度不定义为一个大数字，在判断比较时，最小数字࿰不能通过min获得c;所以我们应该把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; }};