LeetCode 经典题解: 滑动窗口

最新推荐文章于 2025-10-27 21:31:52 发布

原创最新推荐文章于 2025-10-27 21:31:52 发布 · 972 阅读

CC 4.0 BY-SA版权

文章标签：

滑动窗口是解决连续子串 / 子数组优化问题的经典算法，其核心是通过双指针（左边界left、右边界right）维护动态窗口，在遍历过程中动态调整窗口范围，确保窗口满足问题约束（如 “无重复字符”），同时规避暴力枚举的冗余计算。本文以力扣 3 题（无重复字符的最长子串）为载体，从问题定义、算法逻辑、代码实现到复杂度分析，进行拆解，确保每一步推导均有明确依据。

一、问题定义与约束

1. 题目描述

给定一个字符串s，返回其中不包含重复字符的最长子串的长度。

子串：连续的字符序列（区别于子序列，子序列可非连续）；
无重复：子串中任意两个字符的 ASCII 值或 Unicode 值不同；
输入约束：0 ≤ s.length ≤ 5 × 10⁴（需考虑空字符串、超长字符串场景）；
输出：非负整数（最长子串长度，若s为空则返回 0）。

2. 典型测试用例（覆盖边界与常规场景）

输入示例	输出	核心原因
`s = ""`	0	空字符串无有效子串
`s = "a"`	1	单字符子串无重复
`s = "bbbbb"`	1	全重复字符，最长子串为单个字符
`s = "abcabcbb"`	3	最长无重复子串为`"abc"`或`"bca"`等
`s = "abba"`	2	需处理左指针连续收缩（如`right=3`时）

二、暴力解法的局限性

1. 暴力解法逻辑

枚举所有可能的子串：遍历所有起始索引i（0 ≤ i < n）和结束索引j（i ≤ j < n），共生成n(n+1)/2个非空子串；
检查每个子串是否无重复：对每个子串s[i..j]，用哈希集合或数组判断是否存在重复字符；
记录最长无重复子串的长度。

2. 复杂度推导

时间复杂度：枚举子串的时间为O(n²)（n为字符串长度），每个子串的重复检查需遍历j-i+1个字符（最坏O(n)），因此总时间复杂度为O(n²) × O(n) = O(n³)。当n=5×10⁴时，n³=1.25×10¹⁴，远超计算机单次运算的时间上限（约10⁸次 / 秒），必然超时。
空间复杂度：检查重复时使用的哈希集合最多存储n个字符（全不重复场景），故空间复杂度为O(min(m, n))，其中m为字符集大小（如 ASCII 字符集m=128）。

三、滑动窗口算法的逻辑

1. 算法核心思想

通过双指针维护一个满足 “无重复字符” 的窗口，窗口范围为[left, right]（闭区间）：

右指针right：负责 “扩张窗口”，遍历字符串的每个字符，将当前字符尝试加入窗口；
左指针left：负责 “收缩窗口”，当right指向的字符已在窗口内时，右移left并移除窗口内的对应字符，直到窗口恢复 “无重复” 状态；
不变量（Invariant）：在遍历过程中，窗口[left, right]始终是 “以right为右边界的最长无重复子串”，确保每次更新均能记录当前最优解。

2. 算法步骤

阶段 1：初始化（确保初始状态满足约束）

窗口字符存储结构：选用哈希集合char_set，用于O(1)时间判断字符是否在窗口内（规避线性查找的冗余）；
左指针left：初始化为0（窗口左边界起始位置）；
最长长度max_len：初始化为0（无有效子串时返回 0）；
右指针right：从0开始遍历字符串（遍历范围0 ≤ right < n）。

阶段 2：右指针扩张与窗口收缩（维护不变量）

对每个right，执行以下操作：

收缩窗口（确保无重复）：若s[right]已在char_set中（窗口内存在重复），则：
- 移除char_set中s[left]（左边界字符出窗）；
- 右移left（缩小窗口范围）；
- 重复上述两步，直到s[right]不在char_set中（窗口恢复无重复状态）。注：使用while循环而非if，因需处理 “连续重复” 场景（如s="abba"，right=3时需连续收缩left至 2）。
扩张窗口（加入当前字符）：将s[right]加入char_set，此时窗口[left, right]为 “以right为右边界的最长无重复子串”。
更新最长长度：计算当前窗口长度current_len = right - left + 1（闭区间长度公式），若current_len > max_len，则更新max_len = current_len。

阶段 3：遍历结束返回结果

遍历完成后，max_len即为 “无重复字符的最长子串长度”，返回max_len。

3. 算法正确性证明（关键 invariant 验证）

假设在遍历到right = k时，窗口[left_k, k]是 “以k为右边界的最长无重复子串”：

当right = k+1时，若s[k+1]不在[left_k, k]中，则[left_k, k+1]是 “以k+1为右边界的最长无重复子串”；
若s[k+1]在[left_k, k]中，设其位置为p（left_k ≤ p ≤ k），则收缩left至p+1，此时[p+1, k+1]是 “以k+1为右边界的最长无重复子串”（因[left_k, p]包含s[k+1]，无法构成无重复子串）。

由数学归纳法可知，遍历过程中始终维护不变量，最终max_len必然是全局最长无重复子串的长度。

四、代码实现与边界处理

1. 代码实现（含关键注释与逻辑标注）

def lengthOfLongestSubstring(s: str) -> int:
    # 窗口字符存储：哈希集合（O(1)判断存在性）
    char_set = set()
    # 左边界指针（初始为0，窗口左闭）
    left = 0
    # 最长子串长度（初始为0，覆盖空字符串场景）
    max_len = 0
    # 字符串长度（避免多次调用len(s)，提升效率）
    n = len(s)
    
    # 右边界指针遍历（窗口右闭）
    for right in range(n):
        current_char = s[right]
        
        # 收缩窗口：确保当前字符不在窗口内（维护无重复约束）
        while current_char in char_set:
            # 左边界字符出窗
            char_set.remove(s[left])
            # 左边界右移（缩小窗口）
            left += 1
        
        # 扩张窗口：当前字符入窗
        char_set.add(current_char)
        
        # 更新最长长度（当前窗口为[left, right]，长度=右-左+1）
        current_len = right - left + 1
        if current_len > max_len:
            max_len = current_len
    
    # 返回结果（覆盖所有场景：空串、全重复、无重复等）
    return max_len

2. 边界场景代码执行流程（以`s="abba"`为例）

right=0（current_char='a'）：'a'不在空集合，入窗后char_set={'a'}，current_len=1，max_len=1；left=0。
right=1（current_char='b'）：'b'不在集合，入窗后char_set={'a','b'}，current_len=2，max_len=2；left=0。
right=2（current_char='b'）：'b'在集合，执行while：
- 移除s[0]='a'，left=1，仍含'b'；
- 移除s[1]='b'，left=2，集合为空；入窗'b'，current_len=1，max_len保持 2；left=2。
right=3（current_char='a'）：'a'不在集合，入窗后char_set={'b','a'}，current_len=2，max_len保持 2；left=2。

最终返回2，与预期结果一致。

五、复杂度分析

1. 时间复杂度：`O(n)`

右指针right：遍历字符串一次，共n步；
左指针left：仅在窗口收缩时右移，且left始终不小于0、不大于right，最多移动n步；
总操作次数为O(n) + O(n) = O(n)，无冗余计算。

2. 空间复杂度：`O(min(m, n))`

m：字符集大小（如 ASCII 为 128，Unicode 为更大值）；
哈希集合char_set最多存储窗口内的无重复字符：
- 若字符串所有字符不重复（如s="abcde"），则char_set大小为n；
- 若字符集大小m < n（如 ASCII 字符集，m=128），则char_set最大大小为m（因最多存储m个不重复字符）。因此空间复杂度为O(min(m, n))，优于暴力解法的O(n)（当m < n时）。

六、算法适用场景与通用模板

1. 适用场景

滑动窗口（可变窗口 + 求最长）适用于满足以下条件的问题：

问题目标：求 “满足约束的最长连续子串 / 子数组”；
约束条件：可通过双指针动态维护（如 “无重复”“和≥k”“含 k 个不同字符” 等）；
数据类型：字符串或数组（连续序列）。

2. 通用模板（定义可替换组件）

def sliding_window_max(sequence: str | list) -> int:
    # 1. 初始化窗口工具（根据约束选择：集合/哈希表/计数器）
    window_tool = set()  # 示例：无重复约束用集合
    left = 0  # 左边界
    max_result = 0  # 最长结果（初始值根据问题调整）
    n = len(sequence)
    
    # 2. 右边界遍历（扩张窗口）
    for right in range(n):
        current = sequence[right]
        
        # 3. 收缩窗口（维护约束：根据问题修改条件）
        while 约束不满足（如current in window_tool）:
            window_tool.remove(sequence[left])  # 左元素出窗
            left += 1  # 左边界右移
        
        # 4. 扩张窗口（当前元素入窗）
        window_tool.add(current)
        
        # 5. 更新结果（根据问题修改计算逻辑）
        current_len = right - left + 1
        if current_len > max_result:
            max_result = current_len
    
    return max_result

七、关键注意事项（避坑）

数据结构选择：判断 “元素是否在窗口内” 需用哈希集合 / 哈希表（O(1)时间），不可用列表（O(n)时间），否则会退化到O(n²)复杂度；
收缩循环条件：必须用while而非if，处理连续重复场景（如s="abba"）；
边界初始化：max_len初始为0（覆盖空字符串），left初始为0（窗口起始位置）；
复杂度理解：左指针不回头，总遍历次数为O(n)，避免误判为O(n²)（因while循环内left仅移动一次）。

通过以上解析，不仅能掌握力扣 3 题的解法，更能理解滑动窗口算法的核心逻辑与适用边界。若需进一步验证严谨性，可尝试将模板应用于 “最长不含重复数字的子数组”“最长含 1 的子数组（允许替换 k 个 0）” 等同类问题，观察是否满足复杂度与正确性要求。