算法每日双题精讲——滑动窗口（长度最小的子数组，无重复字符的最长子串）

🌟快来参与讨论💬，点赞👍、收藏⭐、分享📤，共创活力社区。 🌟

别再犹豫了！快来订阅我们的算法每日双题精讲专栏，一起踏上算法学习的精彩之旅吧！💪

💯前言

💯滑动窗口的作用

💯长度最小的子数组

题目描述：

⭐解题思路：

🙋这个解题思路是怎么来的呢？

代码实现（以 C++ 为例）：

👀复杂度分析：

💯无重复字符的最长子串

题目描述：

⭐解题思路：

🙋这个解题思路是怎么来的呢？

代码实现（以 C++ 为例）：

👀复杂度分析：

💯总结

💯前言

在算法的领域中，滑动窗口算法犹如一把精巧的钥匙，能够高效地开启许多数组和字符串相关问题的求解之门。今日，我们将聚焦于两道经典题目 ——“长度最小的子数组” 和 “无重复字符的最长子串”，深入领略滑动窗口算法的魅力与应用技巧。

✍当面临在给定数据结构中查找满足特定条件的子结构问题时，滑动窗口算法常常能为我们提供清晰且高效的解题思路。

💯滑动窗口的作用

滑动窗口算法可有趣啦！它用两个同向的指针来定义一个会动的 “窗口” 哦，这个窗口就像一个调皮的😜小精灵，在数组或者字符串里跑来跑去呢。通过不停地调整窗口的大小和位置，它能时刻知道窗口里面元素的情况，这样就能很快找到我们想要的子序列或者子串啦。这种方法可比那种傻傻地把所有可能的子结构都检查一遍的暴力枚举法强多啦，它能让算法的效率像火箭一样🚀飞起来呢！

滑动窗口是利用单调性，用 “同向双指针” 来实现优化的哦。简单来说呢，就是指针只向前走，不会后退哦。

👇操作步骤大概是这样滴：

先把left和right都设成0，
然后把元素放进窗口里，接着判断一下，如果满足条件就缩小窗口，如果不满足就扩大窗口，
最后别忘了更新结果哦。
就这样一直重复，直到把整个数据结构都遍历完。这样就能巧妙地避开那些没必要的计算啦，是不是很聪明呢？😎

💯长度最小的子数组

题目链接👉【力扣】

题目描述：

给定一个包含 n 个正整数的数组和一个正整数 target，找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。若不存在符合条件的子数组，则返回 0。

⭐解题思路：

初始化双指针 left 和 right，均指向数组起始位置，sum 用于记录当前窗口内元素之和，初始化为 0，minLength 记录最小子数组长度，初始化为一个较大值（如 INT_MAX）。
移动 right 指针向右扩展窗口，将新元素累加到 sum 中。
当 sum ≥ target 时，尝试移动 left 指针向右收缩窗口，同时更新 sum。在此过程中，不断比较当前窗口长度与 minLength，若当前长度更小，则更新 minLength。
重复步骤 2 和 3，直到 right 指针到达数组末尾。
最后，若 minLength 仍为初始值，返回 0；否则，返回 minLength。

🙋这个解题思路是怎么来的呢？

我们首先最容易想到解法一：暴力求解

👇现在我们来分析以下数组：

起初我们让left=right=0，此时sum=2，（sum为left到right之间的和）

sum=2 < target,我们让 right++,sum变成了2+3

当right走到这个位置时，sum=2+3+1+2=8>target，我们计算len=right-left ，然后让left++，sum减去第一个left所指的值

sum<target，我们继续让 right++

重复以上步骤，记录最小的len，直到 right<n

代码实现（以 C++ 为例）：

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size(); // 获取数组nums的大小int left = 0; // 滑动窗口的左边界指针，初始化为0int right = 0; // 滑动窗口的右边界指针，初始化为0int sum = 0; // 用于记录当前滑动窗口内元素的总和int len = INT_MAX; // 初始化为INT_MAX，用于记录满足条件的最小子数组长度// 开始移动右边界指针right来扩展滑动窗口while (right < n) {sum += nums[right]; // 将当前右边界指向的元素加入到总和sum中// 当当前滑动窗口内元素总和sum大于等于目标值target时while (sum >= target) {len = std::min(len, right - left + 1); // 更新最小子数组长度len，取当前窗口长度与之前记录的最小值中的较小值sum -= nums[left]; // 将窗口左边界对应的元素从总和sum中减去left++; // 左边界指针向右移动一位，尝试缩小窗口继续寻找更小的满足条件的子数组}right++; // 右边界指针向右移动一位，继续扩展窗口}// 如果len仍然是INT_MAX，说明没有找到满足条件的子数组，返回0；否则返回lenreturn len == INT_MAX? 0 : len;}
};

👀复杂度分析：

时间复杂度： $O(n)$ ，其中 n 为数组长度。最坏情况下，right 指针遍历整个数组一次，left 指针最多也遍历整个数组一次。
空间复杂度： $O(1)$ ，仅需额外常数级别的空间存储指针和变量。

💯无重复字符的最长子串

题目链接👉【力扣】

题目描述：

给定一个字符串 s，找出其中不含有重复字符的最长子串的长度。

⭐解题思路：

初始化 left 和 right 指针指向字符串起始位置，使用 unordered_set<char> 来记录窗口内出现过的字符。
移动 right 指针向右扩展窗口，将新字符插入集合中。
若新插入字符已在集合中，说明出现重复，此时移动 left 指针向右收缩窗口，同时从集合中移除窗口左侧字符，直到窗口内无重复字符。
在每次移动指针后，更新无重复字符的最长子串长度。
重复步骤 2 - 4，直到 right 指针到达字符串末尾。

🙋这个解题思路是怎么来的呢？

我们首先最容易想到解法一：暴力求解

👇现在我们来分析以下字符串：

让left=right=0,创建哈希表

如果right不在hash里面，将right的值存在hash里面，right++

当right所指的值已经在哈希表里了，我们计算len=right-left

接着我们让 left 走到与 right 所指的值的后面，即a的后面

重复以上过程，找到最大的len，直到right<n

代码实现（以 C++ 为例）：

class Solution {
public:// 函数用于计算给定字符串s中的最长无重复字符子串的长度int lengthOfLongestSubstring(string s) {// 创建一个大小为128的数组，用于记录每个字符出现的次数，初始化为0// 假设字符串中的字符ASCII码值范围在0 - 127之间int hash[127 + 1] = {0}; int left = 0; // 滑动窗口的左边界指针，初始化为0int right = 0; // 滑动窗口的右边界指针，初始化为0int ret = 0; // 用于记录最长无重复字符子串的长度，初始化为0int n = s.size(); // 获取字符串s的长度// 开始移动右边界指针right来扩展滑动窗口while (right < n) {// 将右边界指针right指向的字符在hash数组中的计数加1hash[s[right]]++;// 当右边界指针right指向的字符出现次数大于1时，即出现重复字符while (hash[s[right]] > 1) {// 将左边界指针left指向的字符在hash数组中的计数减1，并将左边界指针left向右移动一位hash[s[left++]]--;}// 更新最长无重复字符子串的长度ret，取当前窗口长度（right - left + 1）与之前记录的ret中的较大值ret = std::max(ret, right - left + 1);right++; // 右边界指针right向右移动一位，继续扩展窗口}return ret; // 返回最长无重复字符子串的长度}
};