滑动窗口 | 迎风起降的小站

滑动窗口是一种通过维护连续区间，减少重复遍历的算法技巧，常用于数组和字符串问题。它本质上是双指针的一种应用：左指针和右指针都从左向右移动，通过扩大或缩小窗口来寻找满足条件的区间。

基本思路

滑动窗口通常使用两个指针 left 和 right 表示当前窗口的左右边界，即区间 [left, right]。

右指针不断向右移动，将新的元素加入窗口；当窗口不满足题目要求时，左指针向右移动，将窗口左侧的元素移出，直到窗口重新满足条件。

由于两个指针都只向右移动，每个元素最多进入窗口一次、离开窗口一次，所以在维护窗口的操作可以在 $O(1)$ 时间内完成时，整体时间复杂度通常为 $O(n)$。

常见类型

固定长度窗口：窗口大小始终为 k，右指针每移动一次，左指针也同步移动，常用于计算长度为 k 的连续子数组或子串。
可变长度窗口：窗口大小会根据条件动态变化，通常先移动右指针扩大窗口，再移动左指针缩小窗口，常用于寻找满足条件的最长或最短连续区间。
计数窗口：使用集合、字典或数组记录窗口中的元素及其出现次数，常用于处理字符频率、重复元素和覆盖关系。

题目索引

题号	题目	难度
3	无重复字符的最长子串	中等
438	找到字符串中所有字母异位词	中等

题目记录

无重复字符的最长子串

题号：3
难度：中等

题目描述

给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。

示例

示例 1：

1
2
3

输入：s = "abcabcbb"
输出：3
解释：因为无重复字符的最长子串是 "abc"，所以其长度为 3。"bca" 和 "cab" 也是正确答案。

示例 2：

1
2
3

输入：s = "bbbbb"
输出：1
解释：因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3：

1
2
3

输入：s = "pwwkew"
输出：3
解释：因为无重复字符的最长子串是 "wke"，所以其长度为 3。"pwke" 是子序列，不是子串。

提示

0 <= s.length <= 10^5
s 由英文字母、数字、符号和空格组成

思路 $O(n)$

这道题可以使用类似快慢指针的滑动窗口来解决。使用 [slow, fast] 表示当前窗口，并始终维护这个窗口内没有重复字符。

fast 每轮向右移动一个位置，将新字符加入窗口。如果新字符已经存在于窗口中，就产生了冲突；此时移动 slow，不断移除左侧字符，直到窗口内不再包含重复的 s[fast]。

可以把这个过程理解为：用 fast 扩展窗口并制造冲突，用 slow 缩小窗口并解决冲突。每次窗口恢复为无重复状态后，使用 fast - slow + 1 更新最长长度。

由于 fast 和 slow 都只向右移动，每个字符最多被加入窗口一次、从窗口中移除一次，因此时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

解法

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        slow = 0
        windows = set()
        max_len = 0

        # 右侧扩展窗口
        for fast in range(len(s)):
            # 冲突
            if s[fast] in windows:
                while s[slow] != s[fast]:
                    windows.remove(s[slow])
                    slow += 1

                # 左边界移动到窗口内无 s[fast]
                slow += 1

            # 没有冲突，扩展窗口
            windows.add(s[fast])
            max_len = max(max_len, fast - slow + 1)

        return max_len

找到字符串中所有字母异位词

题号：438
难度：中等

题目描述

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例

示例 1：

1
2
3

输入：s = "cbaebabacd", p = "abc"
输出：[0,6]
解释：起始索引为 0 的子串是 "cba"，它是 "abc" 的异位词；起始索引为 6 的子串是 "bac"，它是 "abc" 的异位词。

示例 2：

1
2
3

输入：s = "abab", p = "ab"
输出：[0,1,2]
解释：起始索引为 0、1、2 的子串分别是 "ab"、"ba"、"ab"，它们都是 "ab" 的异位词。

提示

1 <= s.length, p.length <= 3 * 10^4
s 和 p 仅包含小写字母

思路 $O(n)$

这道题使用固定长度的滑动窗口，窗口大小始终等于 p 的长度。

使用数组 p_count 统计字符串 p 中每个字符出现的次数，再使用数组 win_count 统计当前窗口中每个字符出现的次数。由于字符可能重复，不能使用 set 判断两个字符串是否由相同字符组成，而应该比较每个字符的频率是否一致。

fast 每轮向右移动，将 s[fast] 加入窗口。当窗口长度超过 p 的长度时，移动 slow，并从 win_count 中移除 s[slow]。当窗口长度恰好等于 p 的长度时，比较 win_count 和 p_count：如果两个数组相同，说明当前窗口是 p 的一个异位词，将窗口起始位置 slow 加入结果。

fast 和 slow 都只向右移动，每个字符最多加入和移出窗口一次。由于字符集固定为 26 个小写字母，比较两个频率数组的时间复杂度可以视为 $O(1)$，因此整体时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

解法

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        slow = 0
        result = []
        win_count = [0] * 26
        p_count = [0] * 26

        for i in range(len(p)):
            p_count[ord(p[i]) - ord('a')] += 1

        for fast in range(len(s)):
            win_count[ord(s[fast]) - ord('a')] += 1

            if fast - slow + 1 > len(p):
                win_count[ord(s[slow]) - ord('a')] -= 1
                slow += 1

            if fast - slow + 1 == len(p) and win_count == p_count:
                result.append(slow)

        return result