滑动窗口思想介绍
滑动窗口思想有趣的一个点在于，很多时候都可以通过暴力的方式解决问题，但是暴力的方法往往不会是这个问题的最佳方式，这个思路挺有趣的，很多时候没有一个固定的模板，往往就是见招拆招式的做法，但还是计划在这里做一个汇总，这种思维的训练还是值得多多锻炼的；
滑动窗口(Sliding Window)是一种用于解决数组或字符串中子数组或子串问题的有效算法技巧。它通过维护某个大小的窗口(子数组或子串)，在数组上滑动窗口，以便在不重复计算的情况下，解决问题。
滑动窗口算法的一般思路如下：
- 初始化左指针和右指针，用于定义窗口的范围。
- 移动右指针，扩展窗口，直到满足特定条件(或窗口内的元素满足某些条件)。
- 当窗口满足条件时，如果需要，移动左指针，缩小窗口，直到窗口不再满足条件。
- 在每次移动窗口的过程中，根据窗口内的元素更新所需的结果。
- 滑动窗口的优势在于它在大多数情况下具有线性时间复杂度，相比于暴力遍历所有子数组或子串，它可以大大减少重复计算，从而提高算法的效率。
滑动窗口常见的应用场景包括：
- 找到数组或字符串中的子数组或子串满足特定条件的问题，如求和、平均值等。
- 在字符串中查找特定长度的连续子串或子序列。
- 解决子串匹配问题，如找到包含特定字符的最短子串。
滑动窗口问题
连续子数组最值问题
先看这个问题下的第一个题目：
1
2
3
题目：
- 给定一个数组，数组中只有0和1，给定一个k，可以将k个0翻转为1
- 求经过翻转后整个数组种最长的连续的1的数目；
之所以首先要说这道题，是因为在一次笔试的时候，明明有了解决策略，但是边界问题搞混淆了，没做出来实在可惜；
思路：
- 设定初始边界，分别是左右指针
left、right； right在数组内部不断移动，如果right在数组内对应的值为0，说明右指针先遇到了一个0；- 这时候记录0出现的个数，记录的变量记作
zeroCount，直到0的个数超限，达到了k，这个时候就准备移动左指针left； - 如果左指针
left对应位置的元素是0，我们需要将zeroCount的个数减去1个，因为这个时候窗口内0的个数随着左指针的移动在不断减小； - 直到零的个数等于k，这个时候
left不能再动，此时记录下子数组长； - 不断移动
right直到超限，一旦超限，不断移动left直到零的个数符合要求； - 经过这样连续不断的处理，最终可以处理完整个数组
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int longestOnes(vector<int>& nums, int k) {
int left = 0, right = 0;
int zeroCount = 0; // 该变量用来记录零的数目
int maxOnes = 0; // 最大结果
while (right < nums.size()) {
if (nums[right] == 0) { // 遇到一个零，增加一个统计数目
zeroCount++;
}
while (zeroCount > k) { // 如果数目超过了k个，说明超出了范围
if (nums[left] == 0) {
zeroCount--;
}
left++; // 不断移动窗口左值
}
maxOnes = max(maxOnes, right - left + 1);
right++;
}
return maxOnes;
}
简单吗？真挺简单的；
————————————————————————————————————————————————————再来看一个类似的问题：
1
2
3
4
5
6
7
题目：
- 给定一个含有n个正整数的数组和一个正整数target。
- 找出该数组中满足其和 ≥ target的长度最小的连续子数组，只要求索引连续而并非数据连续，并返回其长度。
- 如果不存在符合条件的子数组，返回0。
注意：
- 题目已经给定范围是正整数了，因此不需要考虑负；
由于题目已经告知全为正数，因此这个问题也是适合用滑动窗口来解决的：
思路：
- 同样给定双指针
left以及right，初始位都是0，初始时窗口内元素的和为nums[0]； - 如果和大于
target，且子数组长已经取到了1，显然没有必要再继续下去了，返回结果； - 如果和小于
target，拓展右边界，right不断移动，此时和随着right的移动不断更新； - 不断移动，移动到和
>=目标值，此时记录下窗口长，如果更小则更新； - 在满足这个条件的情况下，不断更新left指针，直到和又小于
target； - 就这样不停处理，直到
right到终点；
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int minSubArrayLen(int target, const vector<int>& nums) {
int left = 0; // 指向我们要维护的窗口左边
int right = left; // 指向我们要维护的窗口右边
int res = INT_MAX; // 初始结果
int temp_sum = 0;
// 获取初始的窗口长度
while (right < nums.size()) {
temp_sum += nums[right];
if (temp_sum >= target) {
while (temp_sum >= target) {
temp_sum -= nums[left];
left++; // 大于等于目标值的情况下不断移动左窗口
}
res = min(res, right - left + 2); // 移动之后判断情况
if (res == 1) return res; // 到1就不需要再判断了
}
right++; // right是一定要不断移动的
}
return (res == INT_MAX) ? 0 : res;
}
子数组存在性问题
这种题目一般都固定了窗口的大小，题目类型就不详细描述了，直接看题：
1
2
3
4
5
6
7
题目：
- 给你一个整数数组nums和两个整数indexDiff和valueDiff。
- 找出满足下述条件的下标对(i, j)：
-- i != j
-- abs(i - j) <= indexDiff
-- abs(nums[i] - nums[j]) <= valueDiff
- 如果存在，返回true；否则，返回false。
看到题的第一步就是转换题目的意思，这个思想很重要：
- 窗口的长度(说法并不严格)要小于等于
indexDiff； - 窗口左右两边的元素之差的绝对值要小于等于
valueDiff； - 是否存在这么一个窗口？
题目的需求已经明确，接下来就是做滑动处理了，不妨认为i > j；
- 我们要想判断两个值的距离：
|a - b| <= c - 显然，以a为中心，b的范围必然是：
[a - c, a + c] - 也就是说，当判断一个a的时候，我们只需要查找窗口中是否存在这么一个b在上述范围内即可；
- 如果存在，得到结果，如果不存在，判断下一个窗口
- 怎么快速获取到存在性呢？遍历数组显然不是一个好方法，试试空间换时间
- 假设我们通过某些方式保存了窗口内的元素，对于窗口的最右边的元素
- 在窗口内找到
[a - c, a + c]范围内的最小值，也就是通过lower_bound找到大于等于a - c的最小值 - 判断这个值是不是同时也是小于等于
a + c，如果是，恭喜，找到了结果； - 如果不是，就接着判断
- 但是上述这个思路有个很重要的前提，
lower_bound要求元素内有序 - 而我们又需要通过这么一个窗口维护窗口元素信息，显然，想到了set
- 假设元素是
[1 7 3 5 6]，indexDiff为2； - 那么正好要判断的就是窗口
[1 7]中有没有符合范围要求的数 - 我们只需要保证
[1 7]内有序即可
- 假设元素是
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
bool containsNearbyAlmostDuplicate(vector<int>& nums, int indexDiff, int valueDiff) {
int size = nums.size();
set<int> window;
for (int i = 0; i < size; ++i) {
auto it = lower_bound(window.begin(), window.end(), nums[i] - valueDiff); // lower_bound含等于，切记同时要求元素有序，因此不能用无序容器
if (it != window.end() && *it <= (nums[i] + valueDiff)) return true; // 为空这一步不会执行，没找到符合条件的元素这一步也不会执行
window.insert(nums[i]); // 插入元素，这个插入操作保证整个元素有序
if (i >= indexDiff) window.erase(nums[i - indexDiff]); // 超过范围需要清除掉左边界的元素，后面插入进来的始终还是有序
}
return false;
}
这道题这种方法的时间复杂度是最优解法，没想到这个方法处理这个问题还是挺难的；
(未完待续，不断拓展更新)