滑动窗口算法通过双指针维护动态区间，适用于求最短/最长子串等问题。使用left和right指针遍历数组或字符串，right扩展窗口，left收缩窗口，配合哈希表等结构维护区间状态。典型应用包括最长无重复子串、最小覆盖子串等。核心在于根据条件移动指针并更新窗口内数据，时间复杂度通常为O(n)。
滑动窗口算法是一种常用于处理数组或字符串子区间问题的技巧，特别适用于寻找满足条件的最短或最长子串、子数组等问题。在C++中，通过双指针实现滑动窗口非常高效，时间复杂度通常为O(n)。
滑动窗口的基本思想
滑动窗口使用两个指针（left 和 right）维护一个动态窗口，right 指针用于扩展窗口，left 指针用于收缩窗口。通过移动这两个指针，遍历整个数组或字符串，同时维护窗口内的状态。
典型的应用场景包括：
- 找出含有某字符集的最小覆盖子串
- 找出最长无重复字符的子串
- 找出和大于等于目标值的最短子数组
滑动窗口通用模板
以下是一个通用的C++滑动窗口框架，适用于多数子串/子数组问题：
立即学习“C++免费学习笔记（深入）”；
int left = 0, right = 0;
// 根据问题定义所需变量，如哈希表、计数器、当前和等
unordered_map<char, int> window;
<p>while (right < s.size()) {
// 扩展右边界
char c = s[right];
right++;
// 更新窗口数据，如 window[c]++，更新 valid 等</p><pre class='brush:php;toolbar:false;'>// 判断是否需要收缩左边界
while (窗口满足收缩条件) {
// 更新结果（如果需要）
// 收缩左边界
char d = s[left];
left++;
// 更新窗口数据，如 window[d]--
}
}
法语助手旗下的AI智能写作平台，支持语法、拼写自动纠错，一键改写、润色你的法语作文。
31
查看详情
实例：最长无重复字符子串
给定一个字符串，找出其中不含有重复字符的最长子串的长度。
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;
<p>int lengthOfLongestSubstring(string s) {
unordered_set<char> seen;
int left = 0, maxLen = 0;</p><pre class='brush:php;toolbar:false;'>for (int right = 0; right < s.size(); right++) {
while (seen.find(s[right]) != seen.end()) {
seen.erase(s[left]);
left++;
}
seen.insert(s[right]);
maxLen = max(maxLen, right - left + 1);
}
return maxLen;
}
法语助手旗下的AI智能写作平台，支持语法、拼写自动纠错，一键改写、润色你的法语作文。
31
查看详情
int main() {
string s = “abcabcbb”;
cout << lengthOfLongestSubstring(s) << endl; // 输出 3
return 0;
}
说明：使用 set 记录当前窗口中的字符，当遇到重复字符时，不断移动 left 直到无重复为止，并更新最大长度。
实例：最小覆盖子串
给你一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字符的最小子串。
#include <iostream>
#include <string>
#include <unordered_map>>
using namespace std;
<p>string minWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;</p><pre class='brush:php;toolbar:false;'>int left = 0, right = 0;
int valid = 0; // 表示 window 中满足 need 条件的字符个数
int start = 0, len = INT_MAX;
while (right < s.size()) {
char c = s[right];
right++;
if (need.count(c)) {
window[c]++;
if (window[c] == need[c])
valid++;
}
while (valid == need.size()) {
if (right - left < len) {
start = left;
len = right - left;
}
char d = s[left];
left++;
if (need.count(d)) {
if (window[d] == need[d])
valid--;
window[d]--;
}
}
}
return len == INT_MAX ? "" : s.substr(start, len);
}
法语助手旗下的AI智能写作平台，支持语法、拼写自动纠错，一键改写、润色你的法语作文。
31
查看详情
这个实现使用两个哈希表分别记录目标字符需求和当前窗口状态，通过 valid 变量判断是否已覆盖所有目标字符。
基本上就这些。掌握滑动窗口的关键是理解左右指针的移动逻辑和窗口状态的维护方式。根据不同题目调整判断条件和更新策略即可。
暂无评论内容