滑动窗口算法通过双指针维护动态区间，适用于求最短/最长子串等问题。使用left和right指针遍历数组或字符串，right扩展窗口，left收缩窗口，配合哈希表等结构维护区间状态。典型应用包括最长无重复子串、最小覆盖子串等。核心在于根据条件移动指针并更新窗口内数据，时间复杂度通常为O(n)。
滑动窗口算法是一种常用于处理数组或字符串子区间问题的技巧，特别适用于寻找满足条件的最短或最长子串、子数组等问题。在C++中，通过双指针实现滑动窗口非常高效，时间复杂度通常为O(n)。
滑动窗口的基本思想
滑动窗口使用两个指针（left 和 right）维护一个动态窗口，right 指针用于扩展窗口，left 指针用于收缩窗口。通过移动这两个指针，遍历整个数组或字符串，同时维护窗口内的状态。
典型的应用场景包括：
找出含有某字符集的最小覆盖子串找出最长无重复字符的子串找出和大于等于目标值的最短子数组
滑动窗口通用模板
以下是一个通用的C++滑动窗口框架，适用于多数子串/子数组问题：
立即学习“C++免费学习笔记（深入）”；
int left = 0, right = 0;// 根据问题定义所需变量，如哈希表、计数器、当前和等unordered_map window;while (right < s.size()) {// 扩展右边界char c = s[right];right++;// 更新窗口数据，如 window[c]++，更新 valid 等
// 判断是否需要收缩左边界while (窗口满足收缩条件) { // 更新结果（如果需要） // 收缩左边界 char d = s[left]; left++; // 更新窗口数据，如 window[d]--}
}
实例：最长无重复字符子串
给定一个字符串，找出其中不含有重复字符的最长子串的长度。
#include #include #include using namespace std;int lengthOfLongestSubstring(string s) {unordered_set seen;int left = 0, maxLen = 0;
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;
}
int main() {string s = "abcabcbb";cout
说明：使用 set 记录当前窗口中的字符，当遇到重复字符时，不断移动 left 直到无重复为止，并更新最大长度。
实例：最小覆盖子串
给你一个字符串 S 和一个字符串 T，请在 S 中找出包含 T 所有字符的最小子串。
#include #include #include using namespace std;string minWindow(string s, string t) {unordered_map need, window;for (char c : t) need[c]++;
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);
}
这个实现使用两个哈希表分别记录目标字符需求和当前窗口状态，通过 valid 变量判断是否已覆盖所有目标字符。
基本上就这些。掌握滑动窗口的关键是理解左右指针的移动逻辑和窗口状态的维护方式。根据不同题目调整判断条件和更新策略即可。
以上就是c++++中如何实现滑动窗口算法_c++滑动窗口算法实现方法的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1477971.html
微信扫一扫 
支付宝扫一扫 
