每日刷题之优选算法（滑动窗口）

1.滑动窗口讲解

1.定义

:滑动窗口算法是一种常用于解决数组、字符串等序列相关问题的技术，特别适用于那些需要处理连续子序列或区间的情况。滑动窗口的基本思想是：通过维护一个窗口，在数据结构上进行滑动，从而实现特定对区间或子序列的高效遍历。

2.什么是滑动窗口算法？

滑动窗口算法是一种用于给定序列（例如队列或字符串）上突发问题的方法。我们维护一个区间（窗口）并通过“滑动”窗口的起点或终点来更新窗口内容。

通常，滑动窗口有多种类型：

1. 滑动窗口的大小：窗口大小是固定的，只移动窗口的起始位置，逐步获取所有可能的子队列或子串。
2. 动态大小的滑动窗口：窗口的大小不固定，窗口大小随着需求的不断变化，通过移动窗口的起始或结束位置，动态调整窗口范围。

3.如何做滑动窗口问题？

1. 问题类型

滑动窗口算法通常适用于以下几类问题：

• 寻找子队列/子串，满足某些条件（如最大和、最小和、和为特定、满足某个字符频率条件等）。
• 可以通过在一个范围内进行“滑动”操作来动态更新解的状态。

2. 确定窗口定义

滑动窗口的核心是定义一个“窗口”，并决定窗口是如何滑动的。例如：

• 如果是固定大小的窗口，窗口的大小在整个过程中保持不变。
• 如果是动态大小的窗口，窗口的大小是可以变化的，可以是扩展或收缩。

3. 窗口的滑动方式

• 扩展窗口：将窗口的右边界或左边界向外扩展，加入新的元素，直到满足条件特定。
• 收缩窗口：当窗口已经满足某个条件时，可以收缩窗口（通常是移动左边界），以便找到可能的最优解或最小解。

4. 窗口的更新

所有窗口的边界变化时间，更新窗口中的状态信息（例如，子吞吐量的和、子串中的字符频率等）。

5. 结束条件

滑动窗口算法通常会在完成批量或字符串的所有元素后停止，并返回结果。

4.做滑动窗口问题的通用步骤

1. 初始化：
   • 定义左右指针（通常称为left和right）。
   • 定义窗口状态所需的参数，比如窗口的和、窗口内元素频率计数等。
2. 移动右指针扩展窗口：
   • 将新元素加入窗口，更新窗口状态。
3. 查询窗口是否满足条件：
   • 如果满足条件，记录结果（如长度、和、指数等）。
4. 移动左光标缩小窗口：
   • 当窗口不满足条件时，通过移动左指针缩小窗口，同时更新状态。
5. 重复上述过程直到遍历整个队列或字符串。

2.问题讲解：

• 209. 长度最小的子数组
• 3. 无重复字符的最长子串

1.长度最小的子数组

1.题目解析

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

找出该数组中满足其总和大于等于 target 的长度最小的

子数组

 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

2.讲解算法原理

1.在做这类问题时，我们要先考虑如何（right）进窗口，怎么（left）出窗口？

用滑动窗口去演示示例一：

我们先定义left 和 right，用一个变量来记录我们入窗口的和,并让right一直往后走：

sum+=nums[right];

当我们加到第4个数字时：此时sum = 8 > targht(7) 的值，如果我们继续添加nums[right]时，sum的数值会越来越大，此时我们就要考虑出窗口了： sum -= nums[left++];

从此我们就知道了这题是如何用滑动窗口了：

1.进窗口：

用一个变量来记录我们入窗口的和,并让right一直往后走；

2.判断：sum的值是否大于target

成功（符合题目条件），我们就一直更新结果，并记录此结果的len（长度）找到最小值

出窗口：让sum的和去减掉最左边的值来出窗口；

3.一直持续上述两步直到将数组遍历完成；

进窗口 -> 判断 -> 更新结果 ->出窗口 -> 进窗口 -> 判断 -> 更新结果->........

3.编写代码

2.无重复字符的最长子串

1.题目解析

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

2.讲解算法原理

在做上题后，相信大家已经对滑动窗口已经有了一定的了解：

我们还是先考虑如何（right）进窗口，怎么（left）出窗口？

用滑动窗口去演示示例一：

我们先定义left 和 right，统计字符出现的个数，并让right一直往后走：

我们可以看到这组数据中第四个字母a出现了两次；此时我们就要考虑出窗口了，

将最左边的a字母给删除。

从此我们就知道了这题是如何用滑动窗口了：

1.进窗口：

用hash桶来记录我们入窗口中字母的数量,并让right一直往后走；

2.判断：hash桶中记录的字母数量是否大于1

成功（符合题目条件），我们就一直更新结果，并记录此结果的ret（子串长度）找到最大值

出窗口：判断出进入哈希桶中那个字母重复并减掉最左边重复字母来出窗口；

3.一直持续上述两步直到将数组遍历完成；

进窗口 -> 判断 -> 更新结果 ->出窗口 -> 进窗口 -> 判断 -> 更新结果->........

3.编写代码

下期预告：

• 1004. 最大连续1的个数 III
• 1658. 将 x 减到 0 的最小操作数

感兴趣的小伙伴们可以先看看题呦，一起加油！！！