【优选算法系列】第一节.滑动窗口（209. 长度最小的子数组和3. 无重复字符的最长子串）

作者简介：大家好，我是未央；

博客首页：未央.303

系列专栏：优选算法系列

每日一句：人的一生，可以有所作为的时机只有一次，那就是现在！！！！！

---

前言

一、长度最小的子数组

1.1 题目描述

描述：

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

---

提示：

• 1 <= target <= 10^9
• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5

---

示例1：

---

实例2：

---

示例3：

---

1.2 题目解析

1.2.1 算法原理

解题思路：

由于此问题分析的对象是「⼀段连续的区间」，因此可以考虑「滑动窗口」的思想来解决这道题。

让滑动窗口满足：从 i 位置开始，窗口内所有元素的和小于 target （那么当窗口内元素之和

第一次大于等于目标值的时候，就是 i 位置开始，满足条件的最小长度）。

---

解题步骤：

步骤一： 先初始化left，right指针，都指向数组开头元素；

---

步骤二：进窗口。将右端元素划入窗口中，统计出此时窗口内元素的和。

---

步骤三：判断。

情况1： 如果窗口内元素之和大于等于 target ：

先更新结果，然后（出窗口）并且将左端元素划出去的同时继续判断是否满足条件并更新结果（因为左端元素可能很小，划出去之后依旧满足条件），之后继续回到开头进行判断。

情况2： 如果窗口内元素之和不满足条件： right++ ，另下一个元素进入窗口。

注意： 更新结果的位置是不一定的，要根据题具体情况具体分析。

---

图示过程解析：

---

为何滑动窗口可以解决问题，并且时间复杂度更低？

---

（1） 这个窗口寻找的是：以当前窗口最左侧元素（记为 left1 ）为基准，符合条件的情况。也就是在这道题中，从 left1 开始，满足区间和 sum >= target 时的最右侧（记为

right1 ）能到哪里。

（2） 我们既然已经找到从 left1 开始的最优的区间，那么就可以大胆舍去 left1 。但是如

果继续像方法一一样，重新开始统计第二个元素（ left2 ）往后的和，势必会有大量重复

的计算（因为我们在求第⼀段区间的时候，已经算出很多元素的和了，这些和是可以在计算

下次区间和的时候用上的）。

（3） 此时， rigth1 的作用就体现出来了，我们只需将 left1 这个值从 sum 中剔除。从right1 这个元素开始，往后找满足left2 元素的区间（此时 right1 也有可能是满足的，因为 left1 可能很小。 sum 剔除掉 left1 之后，依旧满足大于等于target ）。这样我们就能省掉大量重复的计算。

（4） 这样我们不仅能解决问题，而且效率也会大大提升。

---

时间复杂度：虽然代码是两层循环，但是我们的 left 指针和 right 指针都是不回退的，两者

最多都往后移动 n 次。因此时间复杂度是 O(N) 。

---

1.2.2 代码编写

代码解析：

---

二、无重复字符的最长子串

2.1 题目描述

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

---

提示：

• 0 <= s.length <= 5 * 10^4
• s 由英文字母、数字、符号和空格组成

---

示例1：

---

示例2：

---

示例3：

---

2.2 题目解析

2.2.1 算法原理

算法思路：

研究的对象依旧是一段连续的区间，因此继续使用「滑动窗口」思想来优化。

让滑动窗口满足:窗口内所有元素都是不重复的。

做法:

右端元素ch进入窗口的时候，哈希表统计这个字符的频次︰

• 如果这个字符出现的频次超过1，说明窗口内有重复元素，那么就从左侧开始划出窗口,直到ch这个元素的频次变为1，然后再更新结果。
• 如果没有超过1说明当前窗口没有重复元素，可以直接更新结果

---

解题步骤：

步骤一：

定义一个窗口，用来表示当前的子串。窗口的左边界和右边界分别为left和right。

步骤二：

初始化left和right为0，表示窗口的起始位置。

步骤三：

遍历整个字符串，不断右移right指针，将字符添加到窗口中。

步骤四：

检查窗口中的字符是否重复。如果重复，需要左移left指针，同时将重复字符从窗口中删除，直到窗口中不再有重复字符。

步骤五：

更新最长子串的长度。每次右移right指针时，都需要计算当前窗口的长度，并更新最长子串的长度。

步骤六：

重复步骤3到5，直到right指针到达字符串的末尾。返回最长子串的长度。

---

本题使用了一个HashSet来维护窗口中的字符，以快速判断是否重复。通过不断移动left和right指针，来更新窗口和最长子串的长度。

---

2.2.2 代码编写

代码解析：

---

2.3 题目总结

总结一：

滑动窗口题目中想要创建一个窗口的代码示例；

总结