0 Sliding Windows Basic

  1. 什么是滑动窗口？

    滑动窗口本质上是双指针的特殊形式：两个指针left和right同向移动，维护一个连续的区间[left, right)或[left, right]

    • right负责扩张窗口纳入新元素，left负责收缩窗口排除不合法元素
    • $O(n^2) \Rightarrow O(n)$

  2. 滑动窗口的两种类型：

类型窗口大小典型题
固定窗口窗口大小 k 已知字符串中所有字母异位词
可变窗口窗口大小动态变化无重复字符的最长子串

  1. 什么时候使用滑动窗口？关键词

    前提是问题有单调性：窗口扩大时某个量单调变化(比如和变大、字符种类不减)；如果数组含负数导致"扩大窗口和不一定变大", 滑动窗口就失效了, 得换前缀和 + 哈希

    • 连续子数组/子串
    • 最长/最短的满足某条件的子串（不含重复元素/和大于等于target/至多k个不同元素）
    • 包含/不包含某些字符的子串
    • 固定窗口大小"或"可变窗口大小

  2. 模板：右指针负责扩展窗口，左指针负责收缩窗口，两者配合保证窗口始终满足某种约束

 1def sliding_window(s):
 2    window = {}  # 维护窗口内的状态(计数、和等)
 3    left = 0
 4    ans = 0
 5    for right in range(len(s)):
 6        # 右端点元素进入窗口,更新状态
 7        window[s[right]] = window.get(s[right], 0) + 1
 8        
 9        # 当窗口不满足条件时,收缩左端点
10        while 窗口不合法:
11            window[s[left]] -= 1
12            left += 1
13        
14        # 窗口合法,更新答案
15        ans = max(ans, right - left + 1)
16    return ans

1 无重复字符的最长子串 | Medium

题目：给定字符串 s，找出不含有重复字符的最长子串的长度。

"abcabcbb" → 3（"abc"）；"bbbbb" → 1

思路分析：窗口约束：窗口内不能有重复字符

  • 右指针不断扩展窗口
  • 当窗口内出现重复字符时，左指针收缩，直到没有重复
  • 在每一步更新最大长度

踩坑记录： 想清楚用什么数据结构维护窗口：set or dict? left, right如何移动？

代码：

plan 1：用set维护窗口

 1class Solution:
 2    def lengthOfLongestSubstring(self, s: str) -> int:
 3        char = set()
 4        best = 0
 5        left = 0
 6
 7        for right in range(len(s)):
 8            c = s[right]
 9            while c in char:
10                char.discard(s[left])
11                left += 1
12            char.add(c)
13            best = max(best, right - left + 1)
14        
15        return best

plan 2：用 dict 记录字符最后出现位置，直接跳过

 1class Solution:
 2    def lengthOfLongestSubstring(self, s: str) -> int:
 3        lastseen = {}
 4        best = 0
 5        left = 0
 6
 7        for right, c in enumerate(s):
 8            if c in lastseen and lastseen[c] >= left:
 9                left = lastseen[c] + 1
10            lastseen[c] = right
11            best = max(best, right - left + 1)
12        
13        return best

复杂度：

plan 1：用set维护窗口

  • 时间 O(n)，有 while 循环，但 left 和 right 各自最多移动 n 次，总操作 ≤ 2n
  • 空间 O(|Σ|)（字符集大小，ASCII 则 O(128)）

plan 2：用dict维护窗口

  • 时间：O(n)
  • 空间：O(min(n, Σ))

关联题目：

  • 至多包含两个不同字符的最长子串（LC 159）： 把 set 换成 Counter，当 len(counter) > 2 时收缩
  • 至多包含 K 个不同字符的最长子串（LC 340）： 同上，阈值改为 K

2 长度最小子数组 | Medium

题目: 给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。**如果不存在符合条件的子数组，返回 0

思路分析：

  • 变长滑动窗口常用while更新
  • 全是正数可以用滑动窗口，但是有负数时需要用前缀和 + 二分查找

踩坑记录： 想清楚left更新条件

代码：

 1class Solution:
 2    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
 3        best = float("inf")
 4        left = 0
 5        s = 0
 6        for right, num in enumerate(nums):
 7            s += num             
 8            while s >= target:
 9                best = min(best, right - left + 1)
10                s -= nums[left]
11                left += 1
12
13        return best if best != float("inf") else 0

复杂度：

  • 时间：O(n)
  • 空间：O(1)

前缀和 + 二分查找：O(n logn)

 1class Solution:
 2    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
 3        prefix = [0]
 4        for num in nums:
 5            prefix.append(prefix[-1] + num)
 6        best = float("inf")
 7        for left in range(len(prefix)):
 8            low, high = left + 1, len(prefix)
 9            while low < high:
10                mid = (low + high) // 2
11                if prefix[mid] - prefix[left] >= target:
12                    high = mid
13                else:
14                    low = mid + 1
15            if low < len(prefix):
16                best = min(best, low - left)
17            
18        return best if best != float("inf") else 0

3 Counter + matched 计数法

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

题目：给定字符串 s 和模式串 p，找到 s 中所有 p 的字母异位词的起始下标

s = "cbaebabacd", p = "abc" → [0, 6]（"cba" 和 "bac" 都是 "abc" 的异位词）

思路分析：

  • 异位词 = 字符种类和个数完全相同
  • 窗口固定大小为len(p) $\Rightarrow$ 固定窗口
  • 维护一个长度为 len(p) 的窗口在 s 上滑动，比较窗口内字符的计数和 p 的计数是否相同

踩坑记录： 先想暴力做法怎么做，然后再优化； 左右移动条件一定要想清楚

代码：

plan1：直接比较 Counter，简洁但每次比较 O(26)

 1class Solution:
 2    def findAnagrams(self, s: str, p: str) -> List[int]:
 3        m, n = len(p), len(s)
 4        if n < m:
 5            return []
 6        
 7        target = Counter(p)
 8        windows = Counter(s[:m])
 9        result = []
10
11        if target == windows:
12            result.append(0)
13
14        for i in range(m, n):
15            c = s[i]
16            windows[c] += 1
17            left_char = s[i - m]
18            windows[left_char] -= 1
19            if windows[left_char] == 0:
20                del windows[left_char]
21            if windows == target:
22                result.append(i - m + 1)
23        
24        return result

plan 2：维护 matched 计数（优化到严格 O(n)）

  • 不每次比较整个 Counter，而是维护一个变量 matched 记录"有多少种字符的计数已经匹配"
 1class Solution:
 2    def findAnagrams(self, s: str, p: str) -> List[int]:
 3        m, n = len(p), len(s)
 4        if n < m:
 5            return []
 6        
 7        result = []
 8        target = Counter(p)
 9        windows = Counter()
10        required = len(target)
11        matched = 0
12
13        for i in range(n):
14            c = s[i]
15            windows[c] += 1
16            if c in target and windows[c] == target[c]:
17                matched += 1
18            elif c in target and windows[c] == target[c] + 1:
19                matched -= 1
20            
21            if i >= m:
22                d = s[i - m]
23                if d in target and windows[d] == target[d]:
24                    matched -= 1
25                elif d in target and windows[d] == target[d] + 1:
26                    matched += 1
27                windows[d] -= 1
28                if windows[d] == 0:
29                    del windows[d]
30
31            if matched == required:
32                result.append(i - m + 1)
33        
34        return result

复杂度：

plan1：直接比较 Counter，简洁但每次比较 O(26)

  • 时间： O(n × 26) ≈ O(n)
  • 空间：O(26) ≈ O(1)

plan 2：维护 matched 计数（优化到严格 O(n)）

  • 时间：O(n)
  • 空间：O(Σ)

3.2 字符串的排列 | Medium

题目：给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的 排列。如果是，返回 true ；否则，返回 false 。换句话说，s1 的排列之一是 s2 的 子串 。

思路分析： 本质上就是"判断 s2 里存不存在 s1 的异位词子串"，使用滑动窗口维护

代码：

plan1：直接比较 Counter

 1class Solution:
 2    def checkInclusion(self, s1: str, s2: str) -> bool:
 3        m, n = len(s1), len(s2)
 4        if n < m:
 5            return False
 6        
 7        target = Counter(s1)
 8        windows = Counter(s2[:m])
 9        if target == windows:
10            return True
11        
12        for i in range(m, n):
13            c = s2[i]
14            windows[c] += 1
15            left_char = s2[i - m]
16            windows[left_char] -= 1
17            if windows[left_char] == 0:
18                del windows[left_char]
19            
20            if windows == target:
21                return True
22
23        return False

plan 2：维护 matched 计数

 1class Solution:
 2    def checkInclusion(self, s1: str, s2: str) -> bool:
 3        m, n = len(s1), len(s2)
 4        if n < m:
 5            return False
 6        
 7        target = Counter(s1)
 8        windows = Counter()
 9        required = len(target)
10        matched = 0
11
12        for i in range(n):
13            c = s2[i]
14            windows[c] += 1
15            if c in target and target[c] == windows[c]:
16                matched += 1
17            elif c in target and windows[c] == target[c] + 1:
18                matched -= 1
19
20            if i >= m:
21                d = s2[i - m]
22                if d in target and windows[d] == target[d]:
23                    matched -= 1
24                elif d in target and windows[d] == target[d] + 1:
25                    matched += 1
26                windows[d] -= 1
27                if windows[d] == 0:
28                    del windows[d]
29
30            if matched == required:
31                return True
32            
33        return False

3.3 最小覆盖子串 | Hard

题目：给定两个字符串 s 和 t，返回 s 中的 最短窗口 子串，使得该子串包含 t 中的每一个字符（包括重复字符）。如果没有这样的子串，返回空字符串 ""

input:  s = "ADOBECODEBANC", t = "ABC"
output: "BANC"

思路分析：

窗口大小不固定（可变窗口），而且只要求"覆盖"（t 中每个字符至少出现要求的次数），不要求完全一致，需要考虑更新判断条件

  • 右指针扩展窗口，直到窗口覆盖了 t 的所有字符
  • 然后左指针收缩窗口，尝试找到更小的覆盖子串
  • 重复直到右指针到达末尾

踩坑记录：

  • 求最短 → “合法就缩，边缩边更新"模板：
    • while matched == required 表示当前窗口已经覆盖了 t 的所有字符。这时候我们可以尝试缩小窗口——收缩到刚好不满足条件为止，收缩前的每一步都可能是一个候选答案
  • matched 的更新逻辑：进入时 w_count[c] == t_count[c] 才加（刚好满足），离开时 w_count[d] < t_count[d] 才减（刚好不满足）
  • t 可能有重复字符，如 t = "AABC"，所以必须用 Counter 而不是 set

代码：

 1class Solution:
 2    def minWindow(self, s: str, t: str) -> str:
 3        m, n = len(t), len(s)
 4        if n < m:
 5            return ""
 6        
 7        target = Counter(t)
 8        windows = Counter()
 9        required = len(target)
10        matched = 0
11
12        best = float("inf")
13        left = 0
14        best_start = 0
15
16        for right, c in enumerate(s):
17            windows[c] += 1
18            if c in target and windows[c] == target[c]:
19                matched += 1
20            
21            while required == matched:
22                if right - left + 1 < best:
23                    best = right - left + 1
24                    best_start = left
25                
26                d = s[left]
27                if d in target and windows[d] == target[d]:
28                    matched -= 1
29                windows[d] -= 1
30                if windows[d] == 0:
31                    del windows[d]
32                left += 1
33
34        return s[best_start: best_start + best] if best != float("inf") else ""

复杂度:

  • 时间：O(n)，right 和 left 各自最多走 n 步，均摊每步 O(1)
  • 空间：$O(\Sigma)$，两个 Counter，$\Sigma$ 为字符集大小

4 Counter + matched总结

  1. 共同点：都在一个长字符串里找另一个短字符串的某种匹配，都用了Counter和Sliding Windows。但是我们需要区分是求定长还是变长、最长还是最短，再套模板
  • 字符串的排列：s1 的某个排列是不是 s2 的子串？
    • 判断存不存在一个定长窗口，字符计数和 s1 完全一致 / s2子串是否有s1的异位词
  • 找到字符串中所有字母异位词：找出 s 中所有和 p 互为异位词的子串的起始位置
    • 找出所有定长窗口，字符计数和 p 完全一致 / 找s子串中p异位词的起始位置
  • 最小覆盖子串：找 s 中最短的子串，使得它覆盖 t 中的每个字符
    • 找最短的可变窗口，字符计数至少满足 t 的要求

  1. 排列 vs 异位词：字符种类和数量完全匹配

  2. 算法框架：Counter + matched

    • 用 Counter(t) 统计目标串每种字符需要多少个 → need
    • 用另一个 Counter 维护当前窗口内每种字符有多少个 → window
    • 用整数 matched 记录"有多少种字符的计数已经达标”
    • 用整数 required = len(need) 记录总共需要匹配多少种字符
    • 当 matched == required 时，窗口满足条件

收缩时"先判后减"的对称逻辑 进入窗口是"先加后判"（加完看是否达标），离开窗口是"先判后减"（先看减之前的状态，再执行减法）。顺序反了 matched 就会算错。

  1. 维度一：定长 vs 变长
  • LC 567 / 438：目标串的排列/异位词，长度必然等于目标串长度 $m$，所以窗口大小固定为 $m$。每次 right 右移一格，left 同步右移一格，窗口始终保持 $m$ 个字符。
  • LC 76：只要求"覆盖"，窗口可以比 $t$ 长（多余字符不影响），所以窗口大小不固定。right 负责扩张，left 负责收缩，两者的移动是解耦的。
 1# 定长窗口（LC 567 / 438）
 2if i >= m:
 3    d = s[i - m]       # 左边界位置由 right 和 m 唯一确定
 4    ...                # 弹出一个字符
 5
 6# 可变窗口（LC 76）
 7while matched == required:
 8    d = s[left]        # 左边界独立维护
 9    ...                # 收缩一个字符
10    left += 1
  1. 维度二：完全一致 vs 至少覆盖
  • LC 567 / 438 要求窗口和目标串是排列/异位词，即字符种类和数量完全一致，不能多也不能少。所以进入窗口时需要处理"超了"的情况：
1# 进入窗口
2window[c] += 1
3if c in need and window[c] == need[c]:
4    matched += 1
5elif c in need and window[c] == need[c] + 1:
6    matched -= 1    # 超了，从匹配变成不匹配
  • LC 76 只要求"覆盖"，窗口里某种字符比 t 多是完全合法的。所以进入窗口时不需要 elif 分支：matched 只在"刚好达标"时 +1，之后再多加也不动它：
1# 进入窗口
2window[c] += 1
3if c in need and window[c] == need[c]:
4    matched += 1
5# 没有 elif，因为多了也没关系

  1. 维度三：收缩逻辑与答案更新位置 LC 567（排列判定）：

    • 收缩方式：定长弹出，if i >= m
    • 答案更新：收缩之后检查 matched == required，找到第一个就 return True
    • 遍历结束没找到就 return False

    LC 438（异位词定位）：

    • 收缩方式：定长弹出，if i >= m
    • 答案更新：收缩之后检查 matched == required，每次满足都 result.append(起始下标)
    • 最后返回所有起始下标的列表

    LC 76（最小覆盖子串）：

    • 收缩方式：可变收缩，while matched == required
    • 答案更新：在 while 内部，每次收缩前窗口都是合法的，边缩边记录最短窗口
    • 最后返回最短子串（如果存在）
  • 求最长（或所有位置）→ 不合法才缩，缩完更新答案
  • 求最短 → 合法就缩，边缩边更新答案（答案在 while 里面）
  1. 做题判断流程：

Q1：窗口大小定长还是可变？→ 排列/异位词 = 定长，覆盖/包含 = 可变

Q2：匹配要求完全一致还是至少覆盖？→ 完全一致需要 elif 处理"超了"，覆盖不需要

Q3：求最长/所有位置还是最短？→ 最短则答案在 while 内部更新

维度LC 567（排列判定）LC 438（异位词定位）LC 76（最小覆盖子串）
难度MediumMediumHard
窗口类型定长 $m$定长 $m$可变
匹配要求完全一致完全一致至少覆盖（可以多）
进入窗口 elif需要（超了 matched -= 1）需要不需要
收缩方式if i >= m 定长弹出if i >= m 定长弹出while matched == required
答案更新位置收缩后，找到即 return True收缩后，append 下标while 内部，记录最短
返回值boolList[int]str
时间复杂度$O(n)$$O(n)$$O(n)$
空间复杂度$O(\Sigma)$$O(\Sigma)$$O(\Sigma)$