【你奶奶都能听懂的C语言】第12期 滑动窗口算法
目录
- 开头：
- 1.长度最小子数组
- 2.无重复字符的最长子串
- 3.最大连续1的个数
- 4.将数减到0的最小操作数
- 5.水果成篮
- 6.找到字符串中的异位词
- 7.最小覆盖子串
- 结语：
开头：
ok了，依旧是一个星期至少一篇，今天继续我们的算法学习，这一期实战篇要学习的算法是——滑动窗口
滑动窗口算法本质是用两个左、右指针来动态的维护一个“窗口”（区间），通过题目中具体的条件来更新区间的范围，从而在O(n) 的时间复杂度来解决“子串”相关问题。
滑动窗口的核心步骤：
- 进窗口
- 判断是否符合条件
- 出窗口
- 更新结果
要注意的是，“更新结果”这一步不一定是在“出窗口”的后面执行，要具体题目来定
接下来就开始我们的云刷题：
1.长度最小子数组
看到题目，要让我们求出长度最小的一段子数组，满足 “之和大于等于 target”这个条件
如上图，给这样的一段数组，target=7 ,那如何求出满足题目要求的子数组呢？
看到题目我们就会想到用两个指针循环遍历数组，一旦两个指针中的范围内的数的和大于等于 7 时，记录此时的长度，当遍历完后，就找到了长度最小的子数组，那我们能不能在此基础上优化优化：
如果按照暴力求解的方法，这时候区间中数的和已经等于 target=7 了，要记录此时的区间长度，然后 right 回退到 left 的位置，然后再 left++
这里我们想一想，right 有必要回退到 left 的位置吗？
首先这一段区间是因为多加入了 right 所指向的数而导致了大于等于 target ，如果此时回退了 right 然后再让 left++，再让 right 向前去遍历，最终还是会到达此前的位置，就说明了 right 不需要回退，这就引出了滑动窗口的一个特性——指针不用回退
我们来看看滑动窗口算法是如何优化的：
首先每一次让 right 指向的数进入窗口（进窗口），一旦窗口中数之和大于等于 target 时（判断条件），我们就要记录此时的长度（更新结果），并要缩小窗口大小，让 left++ (出窗口）
如图，此时的窗口就符合条件需要更新，先记录此时的长度为 4，接着让 left ++ ，一直到不符合条件，来动态的维护窗口
具体代码：
2.无重复字符的最长子串
看到要求连续的子串问题，思考思考滑动窗口算法
（这里的暴力求解的优化过程和上一个例题一样，都是指针不回退特征，这里不解释）
- 进窗口： 让 right++
- 判断条件：要让"窗口"（区间）中的字符都不相同
- 出窗口： 让 left ++，直到满足上述条件
- 更新结果：每次记录符合条件的较大窗口长度
最后的长度就是最长的。
要判断窗口中的字符是否是不重复的，可以用哈希表
详见：双指针+哈希表
代码实现：
3.最大连续1的个数
这道题我们最多可以让 k 个 0 变为 1，要求出一段最长的连续 1 的子数组
这道题窗口的调整条件很显然是：窗口中 0 的个数大于 k ,因为如果窗口中 0 的个数小于等于 k 的话，都可以让其变为1
如上图，此时区间中的 0 的个数大于 k=2，此时最长的长度就是画绿线的区间，此时就要开始出窗口，直到窗口中 0 的个数和条件（ <=k )
此时继续进行“进窗口”操作
区间中 0 的个数又大于 k ，重复上述操作。
代码实现：
4.将数减到0的最小操作数
这道题简单来说就是给定一个数 X ，让我们每次操作从一个数组中的左右选一个数，再让 X 减去这个数，问最少经过几次操作让 X 减到 0
如果正向分析，每次要选取左右任意的一个数，不如我们先来数学分析一下：
数组的总和为 sum ，根据上面的分析，我们其实只要让“内部”的数的和为 sum-X ，并求出最长的长度，最后让总长度减去这一段区间（窗口）的长度就是最少操作次数
可以看到我们的 “窗口” 已经出现了
开始进窗口，每次让 right 指向的数加到 sum，判断如果 sum>target ，就要让 left ++ 出窗口
如上图，如果 sum==target ，就要记录此时的窗口长度
代码实现：
5.水果成篮
这道题看上去有点唬人，但其实说的意思是：给定一个数组，要求出一段区间，这段区间内只能有两种数字，求这段区间最长是多少
和上面第二个例题相似，我们要保证区间内的数字种类 <=2，可以利用哈希表记录窗口内的信息
让 right ++ ，进窗口
但满足窗口中数的种类大于 2，此时要缩小窗口，left++，出窗口直到 kinds<=2
代码实现：
6.找到字符串中的异位词
这道题的意思就是要在 s 数组中去找 p 数组的异位词，返回首元素的下标。
何为异位词，就是将 p 中的所有元素重新排列组合：cba ,acb，bac 这些都是 abc 的异位词
我们首先可以用一个数组或者哈希表，将 p 数组中的信息存储到哈希表中
接着可以创建一个窗口，这个窗口的大小（长度）为 p 的长度，窗口的信息也用一个哈希表存储，然后比较这两个哈希表，如果相等，就可以返回 left (下标)
其实逻辑很简单，但是判断两个哈希表是否相等这里我们需要写一个判断函数吗？
可以，但是这样过于麻烦，可以引入一个 count 变量来记录窗口中的有效字符个数如果 count 等于 p 数组的长度，这时候这个窗口内的就是 p 中的异位词
此时 right 对应的 c 进入哈希表
如果 right 指向的值的哈希值是小于等于 hash1 中的值，说明此时这个字符是有效字符，因为无效字符在 hash1 中都没有对应数，所以只有有效字符才会小于等于 hash1 中的值，这时 count++
但此时的窗口大小大于 p 的元素个数，就要让 left 先前一个，出窗口，但是如果要出窗口的这个字符对应的哈希值小于等于 hash1 中的，有效字符就要少一个
代码实现：
7.最小覆盖子串
这道题异与上面那道题，是一段区间只要包含的有 t 数组中的字符，就符合条件。要求出区间长度最短的。
和上道题的思路差不多，但这里我们要自己求出数组 t 中元素的种类，可以在创建hash2 的时候就计算得到
如果这个字符在加加之前为0，那么这就是一个未被统计的元素，种类 kind++
此时当 hash2 中每一个元素都等于 hash1 中的，就要记录初始位置，以及区间长度
代码实现：
结语：
好了，这一期的滑动窗口算法的云刷题就到这里了，感谢您的观看，如果对您有帮助，麻烦点个收藏和赞，我主页有更好康的呦！
