滑动窗口解题技巧：入门篇与经典题目解析

滑动窗口是一种常见的算法技巧，在解决计算机科学中特定类型的字符串问题时非常有效，特别是那些涉及到查找、计数或统计子串中特定字符或子串出现次数的问题。它通常与双指针（两个指针同时移动）的概念相结合，用于维护一个动态变化的子串，以适应题目要求。 滑动窗口的主要应用场景包括但不限于： 1. **最长无重复子串**：寻找字符串中最长的不包含重复字符的连续子串。 2. **字符计数**：在给定的子串中统计特定字符的出现次数。 3. **子串包含问题**：判断一个字符串是否包含另一个给定的子串。 在C++中，使用滑动窗口解题的常见步骤包括： - **初始化数据结构**：使用`unordered_map`，如`need`用于存储字符串中每个字符的需求计数（如出现次数），`window`用于记录当前滑动窗口内的字符及其出现次数。 - **遍历输入字符串**：遍历输入字符串`s`，对于每个字符`c`，更新`need[c]`的计数，并在`window`中检查是否存在该字符。 - **扩展窗口**：将`right`指针向右移动，直到窗口内所有需求字符都被包含。若`c`在`need`中，则将其添加到`window`并检查是否达到需求。 - **收缩窗口**：当窗口内的字符数量等于`need`的大小（即满足需求），开始收缩`left`指针，检查是否还有多余字符。每次收缩后，重新计算`valid`，即有效字符的数量。 滑动窗口的框架通常如下： ```cpp void slidingWindow(string s, string t) { unordered_map<char, int> need, window; // 初始化数据结构 for (char c : t) need[c]++; int left = 0, right = 0; // 定义双指针 int valid = 0; // 记录满足需求的字符数 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()) { char pre = s[left]; // 左侧窗口字符 left++; // 左移 window[pre]--; if (window[pre] < need[pre]) // 如果已不满足需求 valid--; // 有效字符数量减少 } } // 根据窗口内的信息进一步处理问题 } ``` 通过以上步骤，你可以有效地利用滑动窗口策略解决各种字符串问题，掌握这种技术有助于提高编程效率和理解复杂算法背后的逻辑。