滑动窗口与双指针

灵茶山艾府的题单。

一、定长滑动窗口

这类问题的框架可以分为三步

for (int i = 0; i < s.length(); i++) {
    // 1. 进入窗口
    	// 窗口大小不足时的判定
    		// 一方面是防止下标越界
    		// 另一方面是当窗口大小不足k个时不进行计数！ 
    	if (i < k - 1) continue;
    	
    // 2. 更新答案
    // 3. 离开窗口
}

1456 定长子串中元音的最大数目

ts

// 1. s.split('')
// 将字符串拆解为一个字符数组
let s = "hello";
let chars = s.split('');

// 2. reduce
// 遍历数组中每一个元素，并对每个元素执行回调函数
// 回调的参数包括
// accumulator（累加器）、currentValue（当前值）、currentIndex（当前索引，可选）、array（原数组，可选）
chars.reduce((_, char, index) => {});

643 子数组最大平均数Ⅰ

c++

输出结果有精度要求，所以返回值应该带上类型转换(double)

1343 大小为K且平均值大于等于阈值的子数组数目

ts

数组的reduce()方法需要有返回值！！

2090 半径为k的子数组平均值

c++

考虑到测试用例，需要用long长整型声明变量。

ts

// 1 声明数组
let res = Array(nums.length).fill(-1);

// 2 取证（默认除法是带有小数的）
let res = Math.floor(cur / k);

2379 得到K个黑块的最少涂色次数

ts

数组的reduce()方法中不能使用continue。

continue语句只用用在for、while、do-while这类循环语句中，而reduce是一个高阶方法，不能用continue。

2841 几乎唯一子数组的最大和

c++

由于需要统计是否出现重复数字，故使用map类方法。

再次复习一下map和unordered_map的常用方法：

// map用于存储键值对
// map容器中的元素是按照键的顺序**自动排序**的，非常适合需要快速查找和有序数据的场景
// 1. 声明 map 容器
map<key_type, value_type> map;
// 2. 插入元素
map[key] = value;
// 3. 访问元素
value = map[key];
// 4. 遍历map
for (map<key_type, value_type>::iterator it = map.begin(); it != map.end(); it++) {
    cout << it->first << "=>" << it->second << endl;
}
// 5. 检查键是否存在
if (map.find(key) != map.end()) {
   // 键
}
// 6. 删除元素
map.erase(key);
// 7. 清空map
map.clear();
// 8. 获取map的大小
size_t size = map.size();


// unordered_map用于存储键值对
// unordered_map容器不保证元素的排序，但是提供更快的查找速度
// 1. 声明 unordered_map 容器
unordered_map<key_type, value_type> map;
// 2. 插入元素
map.insert({3, "three"});
// 3. 访问元素
string value = map[1];
// 4. 删除元素
map.erase(1);
// 5. 查找元素
auto it = map.find(1);
if (it != map.end()) {
    ...
}

1423 可获得的最大点数

解题思路

1. 正向思维 ⭐⭐⭐⭐

   题目要求是要按顺序从正面或者反面拿牌使得取得的点数最大。由于牌面的点数是固定的，也就是说此时剩下的n - k张牌的点数和是最小的。

   此时，只要求点数和最小的连续n - k张牌即可。

2. 逆向思维

   先计算按正序取牌的总点数，然后依次按倒序取牌，算得最小值。

1652 拆炸弹

解题思路

当k < 0或k > 0 时，窗口都是随着i的增大而向右移动的，两者的不同在于初始窗口的位置不同，所以可以把这两个情况放在一个循环中考虑。

3439 重新安排会议得到最多空余时间 Ⅰ

由于会议之间是不重叠的，所以有n场会议就有n + 1个茶歇时间（包括茶歇时间为0的情况）。调整k次的话，就可以将k + 1段茶歇时间并在一起，得到最长的休息时间。

可以将这个情景抽象为这个问题：有n + 1个空余时间段，合并其中k + 1个连续的空余时间段，得到的最大长度是夺少？（滑动窗口问题！！）

c++

题解中给出了lambda表达式写法， 故复习一下。

// lambda表达式是一种对匿名函数的支持
// 具体形式为：
// [capture](para) -> return-type{body}

// 在这个例子中，使用 [&] 时，Lambda 表达式会以引用的方式捕获外部作用域中的所有变量。这意味着 Lambda 内部使用的变量与外部作用域中的变量是同一个对象，对这些变量的修改会反映到外部作用域中。
// 如果不使用[&]，而是具体写明调用哪些变量，那只是使用了类似声明局部变量的方式，在函数中的改变不影响外部变量的值。
auto get = [&](int i) -> int {
    if (i == 0) {
        return startTime[0];
    }
    if (i == n) {
        return eventTime - endTime[n - 1];
    }
    return startTime[i] - endTime[i - 1];
};

2134 最少交换次数来组合所有的1 Ⅱ

这一题中，1的个数就是一个定长的滑动窗口，我们的任务是要得到当前环中1的数量最多的部分。

c++

copy函数的用法

vector<int> path(nums.size() * 2, 0);
copy(nums.begin(), nums.end(), path.begin());

1297 子串的最大出现次数

注意看，这题有个陷阱（后面的超时就是这个原因）！

如果有一个子串出现了n次，那么这个子串的子串在字符串中出现的次数只多不少。

故，只要考虑要求的最小长度即可！

2653 滑动字数组的美丽值

显然，这题需要用滑动窗口来实现。

在做这题的过程中，使用容器的过程遇到了亿点点小挫折，且听我细细道来。

c++

map的使用

题目的需求是要得到第x小的数值，应该怎么得到呢？

我第一想法是用迭代器迭代x次，但是，窗口中的数值可能是会重复的！

最后debug后得到这样的代码：

auto it = imap.begin(); 
for (int j = 0; j < x - 1; j++) {
    j += it->second - 1;
    if (j < x - 1) it++;
}

set的使用

在set中放入重复的数字是没有响应的！重复的数字有且只能存入一次。

2269 找到一个数字的K美丽值

c++

1. 将int类型变量转为string

   to_string(num);

   将string类型变量转为int

   stoi();

2. 换一个方向思考

   题目是从最高位开始取k数判断是否美丽，不妨从最低k位开始取。

1461 检查一个字符串是否包含所有长度为K的二进制子串

用unordered_set计算当前字符串的子串类型个数。

二、不定长滑动窗口

可以分为这几类：

• 求最长子数组
• 求最短子数组
• 求子数组个数

3 无重复字符的最长子串

这一题需要维护滑动窗口的起点和终点数组，也就是left和right。其中，right由遍历数组时的i体现，我们需要额外声明一个变量min记录左侧的数值。

具体的步骤如下：

1. 使用哈希表维护窗口内出现的字符；
2. 右移right，当新字符和哈希表不冲突时，加入这个字符；
3. 当新字符和哈希表冲突时，右移left，直至left指向冲突字符为止。

c++

复习一下set容器的使用方法

unordered_set<int> uset;

// 插入元素
uset.insert(10);

// 查找元素
auto it = uset.find(20);

// 删除元素
uset.erase(10);

// 检查大小和是否为空
uset.size();
uset.empty();

// 清空
uset.clear();

ts

一个语法糖

// ?? 空值合并操作符
cnt.set(c, (cnt.get(c) ?? 0) + 1);
//在左侧操作数为 null 或 undefined 时，返回右侧操作数；如果左侧操作数不是 null 或 undefined，则返回左侧操作数

3090 每个字符最多出现次数的最长子字符串

与3 无重复字符的最长子串类似。

1493 删掉一个元素以后全为1的最长子数组

设置一个标志位，当只有一个不为1的元素时，滑动窗口的右端点向右移动。

当遇到另一个不为1的元素时，滑动窗口的左端点变更为前一个不为1的元素的右一个位置。

1208 尽可能使字符串相等

以前面四题是类似的思想，也是考虑窗口的左右端点位置，思考路径相同。

904 水果成篮

这个不定长的滑动窗口需要考虑这几个条件：

• 窗口内只有两个类型的水果
• 滑动窗口的两个端点

1695 删除子数组的最大得分

这一题需要考虑的条件是：

• 滑动窗口内不能有重复的元素
• 滑动窗口的两个端点

2958 最多K个重复元素的最长子数组

这一题需要考虑的条件是：

• 滑动窗口内最多有k个重复元素
• 滑动窗口的两个端点

2024 考试的最大困扰度

这一题需要考虑的条件是：

• 滑动窗口中较小的元素不能超过k个

  这一个条件可以通过&&条件来进行判断。

• 滑动窗口的两个端点

1004 最大连续1的个数Ⅲ

这一题需要考虑的条件是：

• 滑动窗口内最多有k个0
• 滑动窗口的两个端点

1658 将x减到0的最小操作数

使用逆向思维，这一题求的是数组两端和为x的最少数的组合，也就是求最长的中间滑动窗口。

这一题需要考虑的条件是：

• 数组nums的和与x的大小关系

  考虑数组nums的和小于x的情况

• 将新的数添加入滑动窗口时，先考虑滑动窗口的总和小于等于要求，然后再考虑是否等于所求的值。

2730 找到最长的半重复子字符串

这一题的要求是滑动窗口至多只能有一对相邻的字符。

所以设置一个标记位，当右端点遍历到一组新的重复字符时，将左端点移动至第一对重复字符的第二个字符上。

2779 数组的最大美丽值

翻译翻译这一个题目，他想要求的就是最长的滑动窗口，使得里面的最小值和最大值的插值小于等于2x。

滑动窗口 + 最值问题，所以这里考虑到最原数组进行排序操作。

1838 最高频元素的频数

这一题想要得到的是：在滑动窗口内，较小的数相加差值变成窗口内的最大值，在总的差值有上限的情况下求得最长的窗口。

这里涉及到排序和极值的问题，所以第一步就是对数组进行排序操作。

我的思路是，初始化一个数组，用于保存相邻数值的差值。

但是，在面对一些比较变态的测试用例的时候（滑动窗口过长时），会出现超时的问题，吃力不讨好。差值的和超过限定值的时候，还得一个一个差值减少，有一定概率超时。

2516 每种字符至少取K个

采用逆向思维，题目要求从两边取最少，也就是求最长的滑动窗口。

对滑动窗口的限制是，'a''b''c'字母的数量有要求，不能超过上限。

2831 找出最长等值子数组

这一题是要查找最长的子数组，这个子数组满足以下要求：

• 数组内包含的数字是相同的
• 最多有k个不同的数值

方法一：双重循环

外层循环遍历滑动窗口的左端点，内层循环遍历滑动窗口的右端点。

非常不幸的是，超时噜。

方法二 空间换时间

将相同数值存储在一个数组中

比如说 num=[1, 3, 2, 3, 1, 3]

3对应的位置为1，3，5，那么对应的数组为pos_lists = [1, 3, 5]

此时选定下标left和right后（）这里指的是在pos_lists中的下标，实际数组长度为right - left + 1，等值子数组的长度为pos_lists[right] - pos_lists[left] + 1，两个的差值就是要删除的字符数。

2904 最短且字典序最小的美丽子字符串

方法一：枚举

从最小的字符串长度k开始遍历，直到找到最短的美丽子字符串

方法二：滑动窗口

如果窗口内的1的个数超过k，或者窗口端点是0，此时可以移动左端点。

c++

• 字典序大小的判定

  直接通过比大小的方式实现

• ranges库

  // 计算范围内满足特定条件的元素数量
  	int count = ranges::count(s, '1')
  // 对范围内的元素进行排序
     	ranges::sort
  // 在范围内查找指定的元素
      ranges::find
  // 对范围内的每个元素应用给定的函数
      ranges::transform

1234 替换子串得到平衡字符串

逆向思维

当去掉滑动窗口中的字符后，剩余字符的数量比正好为1:1:1:1❌

这个思路是错误的！

实际上，只要在除去子字符串后，让剩下的四个字符的数量均小于等于最终的实际值（也就是字符串总长除4）即可。我们要得到的是字符串的长度，而不是要替换的符号数。

这里可以使用枚举法（三重循环，会超时），也可以使用滑动窗口。

滑动窗口

一层循环实现

外层遍历滑动窗口右端点扩大窗口；满足条件时，右移左端点减小窗口直到条件不满足；当右端点遍历到数组末尾时结束遍历操作！

2875 无限数组的最短子数组

这一题的数组是可以无限延展的，需要求一个最小的子串，使这个子串的和为target。

显然，求子串的过程用到了滑动窗口的思想。

这一题的难点在于：如何考虑数组的延展？

我的想法：延展原数组至原长度的n倍，使得此时的数组和大于等于target，此时一定会存在符合要求的子数组了。但是，数组长度超内存限制噜。

想法二：由于这个数组是重复拼接起来的，所以求得的子数组也可能会存在拼接的情况。只要将原数组扩展一倍（考虑了原数组首尾相接的情况）后，在里面找到一个最小的子数组，满足子数组的和是target的因子即可！