滑动窗口（Sliding Window）是一种常用于处理数组或字符串中子序列问题的算法技巧。它通过维护一个窗口来限制待处理的数据范围，从而高效地解决问题，避免重复计算。它的时间复杂度通常为 O(N)，相较于暴力破解（时间复杂度 O(N^2)）大大提升了效率。
如果你还不了解什么是子串或者时间复杂度，可参考以下文章：
- 【计算机科学】什么是子串？全面解析及应用场景
- 【数据结构】时间复杂度和空间复杂度是什么？
滑动窗口的核心思想
滑动窗口可以看作是在数组或字符串上移动的一个固定大小的子区间。通过将窗口在数据上滑动，我们能够逐步考察不同的子区间，进而找到满足条件的解。滑动窗口的两个关键操作是：
- 扩展窗口（Expand Window）：增大窗口的右边界，以包括新的元素。
- 收缩窗口（Shrink Window）：缩小窗口的左边界，以排除不满足条件的元素。
在滑动窗口问题中，通常需要找到满足某些条件的子数组或子字符串的最优解（如最大值、最小值、特定元素组合等）。因此，滑动窗口常用于以下几类问题：
- 最小或最大子数组和
- 找到包含特定字符的最小子串
- 连续子序列的最优解
算法步骤
- 使用两个指针
left和right表示窗口的左右边界。 - 使用一个变量来记录窗口中的字符是否重复。
- 外层循环扩展
right指针，将字符加入窗口。如果满足条件，将其加入窗口；否则，通过移动left指针移除最左边界。 - 统计并记录窗口的最大长度。
算法模板
// l 控制左边界，r 控制右边界，每次循环右边界不断拓展
for (int l = 0, r = 0; r < s.length(); ++r) {// 判断是否需要收缩左边界（check()函数的具体实现）while (l <= r && check()) {// 实现左边界的收缩}// 进行统计操作
}
算法实战：无重复字符的最长子串
题目链接：无重复字符的最长子串
题目描述：给定一个字符串 s，找到其中不包含重复字符的最长子串的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
算法构建
- 使用
left,right两个指针维护左右边界。 - 使用一个哈希集合来维护字符是否出现过。
- 外层循环不断扩展右边界，内层循环判断当前字符是否已经出现过。如果已出现，则不断收缩左边界直到满足条件。
- 将当前字符标记为已出现。
- 计算最长子串（通过右边界和左边界的差值）。
代码实现：
using namespace std;int lengthOfLongestSubstring(const string& s) {int max_length = 0; // 最长子串长度unordered_set<char> char_set; // 用于记录出现的字符int left = 0; // 左边界// 外循环控制右边界for (int right = 0; right < s.length(); ++right) {// 收缩左边界，直到当前字符不再出现while (char_set.find(s[right]) != char_set.end()) {char_set.erase(s[left++]);}char_set.insert(s[right]); // 插入当前字符max_length = max(max_length, right - left + 1); // 更新最大长度}cout << "最长无重复子串的长度为: " << max_length << endl;return max_length;
}
为何 r - l + 1 要额外 + 1
r - l + 1 是为了计算当前不重复子串的长度。
r和l分别是右边界和左边界，表示当前窗口的范围。- 当前窗口的长度是从索引
l到r，但如果直接计算r - l，结果只会包含从l到r-1的元素，因为这个差值不包括右边界r自身。 - 因此，我们需要加上
1来确保当前窗口的长度包含r对应的字符。
例如，假设 l = 2，r = 4，当前窗口是从索引 2 到 4，那么子串的实际长度应该是 4 - 2 + 1 = 3，表示字符在索引 2、3、4 这三个位置。
原理分析
我们可以使用测试用例1来举例：
以此不断类推，可得到最终的 ans 答案为 3。
复杂度分析
由于只需要对 n 访问一次，所以时间复杂度为 O(N)。
在最坏的情况下，char_set 需要存储 n 个字符，因此空间复杂度为 O(N)。
类比暴力枚举
相比常见的暴力枚举，滑动窗口方法高效得多。暴力枚举的例子如下：
class Solution {
public:int lengthOfLongestSubstring(const string& s) {int max_len = 0; // 使用更具语义化的变量名for (int i = 0; i < s.length(); ++i) {int t = getSubstringLength(s, i);max_len = std::max(max_len, t); // 使用 std::max}cout << max_len << endl;return max_len;}private:static int getSubstringLength(const string& s, int index) {int t = 0;unordered_set<char> seen; // 使用 unordered_set 简化for (int i = index; i < s.length(); ++i) {char c = s[i];if (seen.find(c) == seen.end()) {t++;seen.insert(c);} else {return t;}}return t;}
};
暴力枚举的时间复杂度为 O(N^2)，因为外层循环每执行一次，内层循环都会从 index 循环到 n（输入字符串的长度）。总的执行次数为：
n + (n - 1) + (n - 2) + … + 1，其为等差数列，和为 n(n + 1) / 2，因此时间复杂度为 O(N^2)。
在空间复杂度方面，seen 在最坏情况下可能存储 n 个字符，因此复杂度为 O(N)。
总结
滑动窗口算法通过优化重复计算，显著提高了处理子串问题的效率。理解其原理和应用场景，可以帮助我们在算法竞赛及实际编程中更有效地解决问题。
