【优选算法必刷100题】第009~010题（同向双指针：滑动窗口算法）：长度最小的子数组、无重复字符的最长子串问题求解
🔥艾莉丝努力练剑：个人主页
❄专栏传送门：《C语言》、《数据结构与算法》、C/C++干货分享&学习过程记录、Linux操作系统编程详解、笔试/面试常见算法：从基础到进阶
⭐️为天地立心，为生民立命，为往圣继绝学，为万世开太平
🎬艾莉丝的算法专栏简介：
目录
1.2.2.3 为何滑动窗口可以解决问题，并且时间复杂度更低？
滑动窗口（同向双指针）算法
一、滑动窗口的学习要点
二、滑动窗口细节（以009为例）
1、滑动窗口是什么&&什么时候用滑动窗口
2、滑动窗口怎么用？
3、滑动窗口的正确性
4、滑动窗口的时间复杂度优化
009 长度最小的子数组
力扣链接：LCR 008. 长度最小的子数组
（力扣本站同题链接：209. 长度最小的子数组）
力扣题解链接：滑动窗口解决【长度最小的子数组】问题
题目描述：
对比一下——
1.1 题目解析
1.2 算法原理
1.2.1 思路一：暴力解法
1.2.1.1 算法思路
「从前往后」枚举数组中的任意一个元素，把它当成起始位置。然后从这个「起始位置」开始，然后寻找一段最短的区间，使得这段区间的和「大于等于」目标值。
将所有元素作为起始位置所得的结果中，找到「最小值」即可。
1.2.1.2 暴力算法代码实现
代码演示如下——
//暴力写法 class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { // 记录结果 int ret = INT_MAX; int n = nums.size(); // 枚举出所有满足和大于等于 target 的子数组[start, end] // 由于是取到最小，因此枚举的过程中要尽量让数组的长度最小 // 枚举开始位置 for (int start = 0; start < n; start++) { int sum = 0; // 记录从这个位置开始的连续数组的和 // 寻找结束位置 for (int end = start; end < n; end++) { sum += nums[end]; // 将当前位置加上 if (sum >= target) // 当这段区间内的和满足条件时 { // 更新结果，start 开头的最短区间已经找到 ret = min(ret, end - start + 1); break; } } } // 返回最后结果 return ret == INT_MAX ? 0 : ret; } };时间复杂度：O(n^2)，空间复杂度：O(1)。
1.2.2 思路二：滑动窗口
1.2.2.1 算法思路
由于此问题分析的对象是「一段连续的区间」，因此可以考虑「滑动窗口」的思想来解决这道题。
让滑动窗口满足：从i位置开始，窗口内所有元素的和小于target（那么当窗口内元素之和第一次大
于等于目标值的时候，就是位置开始，满足条件的最小长度）。
做法：将右端元素划入窗口中，统计出此时窗口内元素的和——
（1）如果窗口内元素之和大于等于target：更新结果，并且将左端元素划出去的同时继续判
断是否满足条件并更新结果（因为左端元素可能很小，划出去之后依旧满足条件）；
（2）如果窗口内元素之和不满足条件：right++，另下一个元素进入窗口。
1.2.2.2 滑动窗口算法代码实现
代码演示如下——
//滑动窗口写法 class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int n = nums.size(), sum = 0, len = INT_MAX; //细节，定义0最终结果就是0 for (int left = 0, right = 0; right < n; right++) { sum += nums[right];//进窗口 while (sum >= target)//判断 { len = min(len, right - left + 1);//更新结果 sum -= nums[left++];//出窗口 } } //时间复杂度O(n) return len == INT_MAX ? 0 : len; } };时间复杂度：O(n)，空间复杂度：O(1)。
1.2.2.3 为何滑动窗口可以解决问题，并且时间复杂度更低？
1、这个窗口寻找的是：以当前窗口最左侧元素（记为1eft1）为基准，符合条件的情况。也就是在
这道题中，从left1开始，满足区间和sum>=target时的最右侧(记为righti）能到哪里。
2、我们既然已经找到从left1开始的最优的区间，那么就可以大胆舍去left1。但是如果继续像方法1一样，重新开始统计第二个元素（1eft2）往后的和，势必会有大量重复的计算（因为我们在求第一段区间的时候，已经算出很多元素的和了，这些和是可以在计算下次区间和的时候用上的）。
3、此时，rigth1的作用就体现出来了，我们只需将left1这个值从sum中剔除。从right1这个元素开始，往后找满足left2元素的区间(此时right1也有可能是满足的，因为left1可能很小。sum剔除掉left1之后，依l旧满足大于等于target）。这样我们就能省掉大量重复的计算。
4、这样我们不仅能解决问题，而且效率也会大大提升。
时间复杂度：虽然代码是两层循环，但是我们的left指针和right指针都是不回退的，两者最多都往
后移动n次，也就是说，时间复杂度的最坏情况就是O(N)，因此时间复杂度是O(N)。
1.3 博主手记——过程推算
本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下手记的推导过程！最好做题的过程中自己也推导一遍！！！自己推导很重要！
010 无重复字符的最长子串
力扣链接：3. 无重复字符的最长子串
力扣题解链接：用滑动窗口+哈希表解决【无重复字符的最长子串】问题
题目描述：
2.1 题目解析
2.2 算法原理
2.2.1 思路一：暴力解法
2.2.1.1 算法思路
枚举「从每一个位置」开始往后，无重复字符的子串可以到达什么位置。找出其中长度最大的即可。
在往后寻找无重复子串能到达的位置时，可以利用「哈希表」统计出字符出现的频次，来判断什么时候子串出现了重复元素。
2.2.1.2 算法代码演示
//解法一（暴力求解）（不会超时，可以通过） class Solution { public: int lengthOfLongestSubstring(string s) { int ret = 0; // 记录结果 int n = s.length(); // 1. 枚举从不同位置开始的最长重复子串 // 枚举起始位置 for (int i = 0; i < n; i++) { // 创建⼀个哈希表，统计频次 int hash[128] = { 0 }; // 寻找结束为⽌ for (int j = i; j < n; j++) { hash[s[j]]++; // 统计字符出现的频次 if (hash[s[j]] > 1) // 如果出现重复的 break; // 如果没有重复，就更新 ret ret = max(ret, j - i + 1); } } // 2. 返回结果 return ret; } };时间复杂度：O(n^2)，空间复杂度：O(1)。
2.2.2 思路二：滑动窗口
2.2.2.1 算法思路
研究的对象依旧是一段连续的区间，因此继续使用「滑动窗口」思想来优化。
让滑动窗口满足：窗口内所有元素都是不重复的。
做法：右端元素ch进入窗口的时候，哈希表统计这个字符的频次：
（1）如果这个字符出现的频次超过1，说明窗口内有重复元素，那么就从左侧开始划出窗口，直到ch这个元素的频次变为1，然后再更新结果。
（2）如果没有超过，说明当前窗口没有重复元素，可以直接更新结果。
2.2.2.2 算法代码实现
class Solution { public: int lengthOfLongestSubstring(string s) { int hash[128] = {0}; int left = 0, right = 0, n = s.size(); int ret = 0; // 数组模拟哈希表 while (right < n) { // 进入窗口 hash[s[right]]++; // 判断 while (hash[s[right]] > 1) hash[s[left++]]--; // 出窗口 // 更新结果 ret = max(ret, right - left + 1); // 让下一个元素进入窗口 right++; } return ret; } };时间复杂度：O(n)，空间复杂度：O(1)。
2.3 博主手记——过程推算
本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下手记的推导过程！最好做题的过程中自己也推导一遍！！！自己推导很重要！
结尾
往期回顾：
【优选算法必刷100题】第007~008题（双指针算法）：三数之和、四数之和问题求解
结语：不要忘记给博主来个“一键四连”哦！
🗡博主在这里放了一只小狗，大家看完了摸摸小狗放松一下吧！🗡
૮₍ ˶ ˊ ᴥ ˋ˶₎ა
