【数据结构】滑动窗口算法详解：高效解决子串问题

滑动窗口（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;
    }
};