滑动窗口算法详解与LeetCode实战

"滑动窗口技巧进阶" 滑动窗口是一种在数组或字符串中寻找满足特定条件的子序列的有效算法。这个技术常用于求解一些问题，如查找无重复字符的最长子串、找到字符串中所有字母异位词或者解决最小覆盖子串等问题。在LeetCode上，滑动窗口广泛应用于字符串处理的题目。 滑动窗口的基本思想是维护一个窗口，该窗口在数组或字符串上从左向右移动。窗口的左右边界分别由变量`left`和`right`表示，初始时`left = right = 0`。每次移动窗口的右侧边界`right`，然后更新窗口内的信息，当窗口满足某些条件时，可能需要收缩窗口的左侧边界`left`。 #### 滑动窗口算法框架 以下是一个通用的滑动窗口算法模板： ```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()) { // c 是将移入窗口的字符 char c = s[right]; // 右移窗口 right++; // 进行窗口内数据的一系列更新 // ***debug输出的位置*** printf("window: [%d,%d)\n", left, right); /********************/ // 判断左侧窗口是否要收缩 while (windowNeedShrink) { // d 是将移出窗口的字符 char d = s[left]; // 左移窗口 left++; // 进行窗口内数据的一系列更新 } } } ``` 在上述模板中，我们需要根据具体问题定义`windowNeedShrink`条件，并相应地更新`window`映射表。例如，在最小覆盖子串问题中，`windowNeedShrink`条件是窗口内字符与目标字符串`t`的字符需求不匹配。同时，我们需要跟踪窗口内满足条件的元素个数（`valid`）以及窗口的起始位置。 #### 1.7.1 最小覆盖子串 对于LeetCode上的76题【最小覆盖子串】，我们需要找到一个最短的子串，该子串包含给定目标字符串`t`的所有字符。这个问题可以使用滑动窗口来解决： ```cpp string minWindow(string s, string t) { unordered_map<char, int> need, window; for (char c : t) need[c]++; int left = 0, right = 0; int valid = 0; int minLength = INT_MAX, start = 0; // 记录最小长度子串的起始位置和长度 int minStart = 0; while (right < s.size()) { char c = s[right]; if (need.count(c)) { window[c]++; if (window[c] == need[c]) valid++; } // 如果窗口满足条件，更新最小长度子串 if (valid == need.size()) { // 当前子串长度 int currentLength = right - left + 1; // 更新最小长度子串 if (currentLength < minLength) { minLength = currentLength; minStart = left; } // 移除左侧无效字符 char d = s[left]; if (need[d] && window[d] > need[d]) { window[d]--; valid--; } } right++; left = right - valid; } return minLength == INT_MAX ? "" : s.substr(minStart, minLength); } ``` 在这个版本的滑动窗口算法中，我们维护了一个有效的计数器`valid`，表示当前窗口内满足条件的字符个数。当`valid`等于目标字符串`t`的字符种类数时，我们找到了一个可能的解，然后检查并更新最小长度子串。同时，窗口左侧的无效字符（即已超过需求量的字符）会被移除。 通过这个模板和例子，你可以看到滑动窗口算法如何应用到不同的LeetCode问题中。熟悉这个框架并理解其核心逻辑，有助于你在面对类似问题时快速解决问题。记住，关键在于理解何时扩展窗口，何时收缩窗口，并根据具体问题调整窗口大小和更新条件。