什么是滑动窗口问题？
滑动窗口是一种常用的算法技术，特别适用于处理数组或字符串等线性结构中的子集问题。它通过维护一个“窗口”来跟踪满足某种条件的元素，从而高效地解决问题。以下是滑动窗口的基本概念和应用场景：
基本概念
- 窗口的定义
- 窗口可以视为一个子数组或者子字符串，其大小可以根据需要动态调整；
- 窗口的两端通常用两个指针来表示，指针的位置决定了当前窗口的范围；
- 扩展与收缩
- 移动右指针以增加窗口的大小，通常用于包含更多元素满足条件；
- 收缩窗口：移动左指针以减少窗口的大小，通常用于去掉多余的元素，知道满足条件
应用场景：
- 固定大小的窗口：在数组中查找固定长度的子数组的最大值、最小值、和等。
- 动态大小的窗口: 在字符串中查找满足特定条件的最长或最短子串，如无重复字符的最长子串、包含所有字符的最小窗口等。
1.无重复字符的最长字串
思路分析：将不重复字串的长度转化为索引距离的计算
- 创建一个哈希表mp，用来存储字符及其最新索引；
- 循环遍历每个字符s[i]
- 检查它是否存在于哈希表中：如果存在，则说明字符重复，之前的字串成为了废物，我们就需要更新不重复字串的起始位置为当前字符的下一个位置，确保st始终指向不重复子串的起始位置。
- 当然还需要更新哈希表中该字符的最新索引为当前索引i；
- 最后就是计算字串的长度即i - st + 1,并与res更新为最大值（因为子串很多，要求的是最长不重复字符的字串）
具体实现代码（详解版）：
class Solution {
public:int lengthOfLongestSubstring(string s) {unordered_map<char,int> mp;//存储字符及其最新索引int res = 0,st = 0;//记录结果以及不重复子串的起始索引for(int i = 0 ; i < s.size() ; i ++){//如果字符已经出现过if(mp.find(s[i]) != mp.end()){st = max(st,mp[s[i]] + 1);//更新起始索引}mp[s[i]] = i;//更新当前字符的索引res = max(res,i - st + 1);//计算当前长度}return res;}
};
2.找到字符串中所有字母异位词
思路分析：
- 定义字符频率数组pCoun和sCount，分别用于存储字符串p中每个字符的频率和当前窗口（字符串s中的字串）中每个字符的频率。
- 初始化字符频率
- 第一个循环遍历 p，更新 pCount 中字符的频率。
- 第二个循环初始化窗口的字符频率，窗口大小与 p 相同。
- 关键的滑动窗口
- 通过遍历字符串 s，在每次迭代中检查当前窗口的字符频率是否与 pCount 相等
- 如果相等，说明当前窗口是p的异位词，记录起始索引i - p.size();
- 随后，更新sCount，将当前字符加入窗口并移除窗口的第一个字符。
- 在循环结束后，检查最后一个窗口是否也是一个异位词，如果是，记录其起始索引。
注意
1.为什么要从p.size开始- 从 p.size() 开始的原因是因为我们需要形成一个完整的窗口，大小等于字符串 p 的长度。如果从 0 开始，我们在第一次循环中就会尝试访问 s 中从 0 到 p.size() - 1 的字符，但此时 sCount 还未完全初始化。只有当 i 达到 p.size() 时，窗口的大小才会正确，能够进行比较和更新。
2.如何移除旧字符？-sCount[s[i - p.size()] - ‘a’]–;
s[i - p.size()] 获取的是当前窗口左侧字符的索引，即在这个窗口的前一部分（即已经滑出窗口的字符）。sCount[s[i - p.size()] - ‘a’]-- 把这个字符的频率减 1，表示它在窗口中不再出现。
具体实现代码（详解版）：
class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> result;if (s.size() < p.size()) return result;// 26个字母的频率数组：大小为26，初始值为0vector<int> pCount(26, 0), sCount(26, 0);// 初始化字符频率for (char c : p) pCount[c - 'a']++;for (int i = 0; i < p.size(); i++) sCount[s[i] - 'a']++;// 滑动窗口//p.size() 开始的原因是因为我们需要形成一个完整的窗口，大小等于字符串 p 的长度for (int i = p.size(); i < s.size(); i++) {if (sCount == pCount) {result.push_back(i - p.size());}// 更新窗口sCount[s[i] - 'a']++; // 加入新字符sCount[s[i - p.size()] - 'a']--; // 移除旧字符}// 最后一个窗口的比较if (sCount == pCount) {result.push_back(s.size() - p.size());}return result;}
};
这道题目的难度还是比较大的（相对前一道题目），关键在于滑动窗口的设置比较难想（滑动窗口的大小与p的长度一样），然后要不断往后话滑动并且更新窗口。对于26个字母的频率数组也是很有想法，使得异位词的判断变得很方便。要积累起来~
