目录
引言
定义：滑动窗口是指通过左右两个指针（或索引）来标记窗口的左右边界，随着指针的移动，窗口内的元素不断变化，从而实现对数组或字符串中连续子序列的操作。
特点：
- 连续性：窗口内的元素在位置上是连续的。
- 动态性：窗口的大小（即左右边界之间的距离）可以动态变化，以适应不同的问题需求。
- 高效性：通过滑动窗口技术，可以将一些原本需要嵌套循环的问题转化为单层循环问题，从而降低时间复杂度，提高效率。
核心思想
滑动窗口的核心思想在于通过维护一个窗口，使得窗口内的元素满足特定的条件（如和、最大值、最小值、无重复字符等），并随着指针的移动不断调整窗口的大小，以找到满足条件的最优解（如最长子串、最短子数组等）。
使用场景
滑动窗口技术适用于解决以下类型的问题：
- 在数组或字符串中查找满足特定条件的连续子序列（如最长无重复字符子串、最小覆盖子串等）。
- 计算连续子序列的某种统计量（如和、平均值、最大值、最小值等）。
解题步骤
使用滑动窗口解题时，通常遵循以下步骤：
- 初始化窗口：确定左右指针的初始位置，以及窗口的初始大小（如果有的话）。
- 移动右指针：通过移动右指针来扩展窗口，直到窗口内的元素满足特定条件或右指针到达数组/字符串的末尾。
- 判断与调整：在每次移动右指针后，判断窗口内的元素是否满足条件。如果不满足条件，则通过移动左指针来缩小窗口，直到窗口内的元素重新满足条件。
- 更新结果：在窗口满足条件时，根据题目要求更新结果（如记录最长子串的长度、计算子数组的和等）。
- 重复步骤2-4：直到右指针到达数组/字符串的末尾，完成所有可能的窗口滑动。
经典例题
1、无重复字符的最长子串（LeetCode 3）
题目描述：
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
解题思路：
-
初始化：设置最长子串长度为0，使用哈希集合（
unordered_set）来存储当前窗口内的字符，以及两个指针（左指针left和右指针right）来定义窗口的边界。 -
遍历字符串：通过右指针
right遍历整个字符串。 -
维护窗口无重复：在每次移动右指针时，检查当前字符是否已存在于哈希集合中。
- 如果存在，说明遇到了重复字符，此时需要移动左指针
left来缩小窗口，并从哈希集合中删除左指针指向的字符，直到窗口内不再包含重复字符。 - 如果不存在，将当前字符添加到哈希集合中。
- 如果存在，说明遇到了重复字符，此时需要移动左指针
-
更新最长子串长度：在每次成功添加新字符到哈希集合后，计算当前窗口的长度（
right - left + 1），并与之前记录的最长子串长度进行比较，更新最长子串长度。 -
返回结果：遍历结束后，返回记录的最长子串长度。
#include <string>
#include <unordered_set>
#include <algorithm>
class Solution {
public:
int lengthOfLongestSubstring(std::string s) {
int maxLength = 0;
std::unordered_set<char> charset;
int left = 0; // 左指针
for (int right = 0; right < s.size(); ++right) {
// 如果字符已存在于集合中，则移动左指针，并从集合中删除对应的字符
while (charset.find(s[right]) != charset.end()) {
charset.erase(s[left]);
left++;
}
// 添加新字符到集合中，并更新最长子串的长度
charset.insert(s[right]);
maxLength = std::max(maxLength, right - left + 1);
}
return maxLength;
}
};2、找到字符串中所有字母异位词（LeetCode 438）
题目描述：
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
解题思路：
-
初始化：首先，我们检查
s和p是否为空，或者s的长度是否小于p的长度，因为这些情况下不可能存在任何符合条件的子串。接着，我们使用两个哈希表pCount和windowCount来分别记录p中每个字符的出现次数和当前滑动窗口中每个字符的出现次数。 -
滑动窗口：我们维护一个左边界
left和一个右边界right来定义当前的滑动窗口。我们还使用一个变量matched来记录当前窗口中与p完全匹配的字符种类数。 -
扩展窗口：在每一步中，我们首先将右边界的字符加入窗口（即更新
windowCount），并检查这个字符是否在p中出现。如果是，并且窗口中该字符的数量与p中相同，则matched增加 1。 -
缩小窗口：然后，我们检查窗口的大小是否已经达到了
p的长度。如果是，我们检查matched是否等于p中不同字符的种类数（即pCount.size()），如果是，说明当前窗口是一个完整的异位词，我们将左边界的索引（即left）加入结果集。接着，我们将左边界的字符移出窗口（即更新windowCount和matched），并向右移动左边界。 -
循环继续：我们继续向右移动右边界，重复上述过程，直到右边界超出
s的范围。 -
返回结果：最后，我们返回所有符合条件的子串起始索引的集合。
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> result;
if (s.empty() || p.empty() || s.length() < p.length()) {
return result;
}
unordered_map<char, int> pCount, windowCount;
for (char c : p) {
pCount[c]++;
}
int left = 0, right = 0, matched = 0;
while (right < s.length()) {
// 右边界字符加入窗口
char rChar = s[right];
if (pCount.count(rChar)) {
windowCount[rChar]++;
if (windowCount[rChar] == pCount[rChar]) {
matched++;
}
}
// 当窗口大小达到p的长度时
if (right - left + 1 == p.length()) {
// 如果当前窗口是一个完整的anagram
if (matched == pCount.size()) {
result.push_back(left);
}
// 左边界字符离开窗口
char lChar = s[left];
if (pCount.count(lChar)) {
if (windowCount[lChar] == pCount[lChar]) {
matched--;
}
windowCount[lChar]--;
}
left++;
}
right++;
}
return result;
}
};