滑动窗口算法：高效解决字符串子区间问题

1. 滑动窗口算法核心思想解析

滑动窗口（Sliding Window）是解决字符串和数组子区间问题的高效算法范式。它的核心在于维护一个动态变化的窗口，通过左右指针的协同移动来避免重复计算，将时间复杂度从暴力解法的O(n²)优化到O(n)。

1.1 算法适用场景

滑动窗口特别适合解决以下三类问题：

1. 固定长度子串匹配：如567题需要找到长度固定的排列子串
2. 可变长度最优解：如424题寻找满足条件的最长子串
3. 最小覆盖窗口：如76题需要涵盖目标字符的最短子串

关键洞察：当问题可以转化为"在序列中寻找满足特定条件的连续子区间"时，滑动窗口往往是最佳选择。

1.2 双指针协同机制

窗口通过左右指针(left, right)界定，移动策略分为三种：

1. 右扩左跟：右指针主动扫描，左指针被动跟进（567题）
2. 右扩左缩：右指针探索时左指针可能回缩（424、76题）
3. 交替移动：根据条件交替移动左右指针（76题优化版）

# 通用滑动窗口模板 left = 0 for right in range(len(s)): # 处理右指针新纳入元素 update(window, s[right]) # 根据条件调整左指针 while window_needs_shrink: # 记录当前窗口状态 record(window) # 处理左指针移出元素 remove(window, s[left]) left += 1

2. 567.字符串的排列深度解析

2.1 问题重述与转化

题目要求判断s2是否包含s1的某个排列，等价于：

• 在s2中找到长度为len(s1)的子串
• 该子串的字符组成与s1完全相同（顺序无关）

2.2 频次数组的妙用

使用两个长度26的数组分别统计：

• record：s1中各字符出现次数
• win：当前窗口内字符出现次数

def checkInclusion(s1: str, s2: str) -> bool: n = len(s1) record = [0] * 26 for c in s1: record[ord(c)-97] += 1 # 'a'的ASCII码为97 win = [0] * 26 left = 0 for right in range(len(s2)): win[ord(s2[right])-97] += 1 # 维持固定窗口大小 if right - left + 1 > n: win[ord(s2[left])-97] -= 1 left += 1 if win == record: return True return False

2.3 复杂度优化分析

虽然每次比较两个长度为26的数组，但：

1. 比较操作是O(1)的，因为26是常数
2. 右指针遍历整个s2是O(n)
3. 总体时间复杂度保持为O(n)

实战技巧：Python中列表比较比逐个元素比较更高效，因为解释器底层用C实现。

3. 424.替换后的最长重复字符进阶解法

3.1 问题转化思路

题目可转化为：寻找一个窗口，使得窗口长度 - 最高频字符数 ≤ k。这表示该窗口最多通过k次替换就能变成全相同字符。

3.2 关键优化点解析

常规思路每次收缩窗口时重新计算maxCount会导致O(n²)复杂度。优化策略：

• 不实时更新maxCount，而是维护历史最大值
• 即使当前maxCount不准确，也不会影响最终结果
• 因为结果只关心最大可能窗口，宽松的判断条件不会错过最优解

def characterReplacement(s: str, k: int) -> int: count = [0] * 26 left = max_count = result = 0 for right in range(len(s)): count[ord(s[right])-65] += 1 max_count = max(max_count, count[ord(s[right])-65]) if right - left + 1 - max_count > k: count[ord(s[left])-65] -= 1 left += 1 result = max(result, right - left + 1) return result

3.3 复杂度证明

该算法的时间复杂度为O(n)因为：

• 右指针遍历整个字符串一次
• 左指针最多移动n次
• 每个字符最多被左右指针各访问一次

4. 76.最小覆盖子串工程实践

4.1 需求分析与建模

问题要求找到s中包含t所有字符的最短子串，需要考虑：

1. 字符频次匹配（而不仅是字符存在）
2. 子串的连续性要求
3. 可能存在重复字符的情况

4.2 双哈希表解法

使用两个字典分别记录：

• need：t中各字符所需数量
• window：当前窗口中各字符已有数量

def minWindow(s: str, t: str) -> str: from collections import defaultdict need = defaultdict(int) for c in t: need[c] += 1 window = defaultdict(int) left = valid = 0 start = 0 min_len = float('inf') for right, c in enumerate(s): if c in need: window[c] += 1 if window[c] == need[c]: valid += 1 while valid == len(need): if right - left + 1 < min_len: min_len = right - left + 1 start = left left_char = s[left] if left_char in need: if window[left_char] == need[left_char]: valid -= 1 window[left_char] -= 1 left += 1 return s[start:start+min_len] if min_len != float('inf') else ""

4.3 性能优化技巧

1. valid计数器：避免每次全量检查字符匹配情况
2. 字典预初始化：提前为need中的字符建立window键
3. 边界处理：当t比s长时直接返回空字符串

5. 滑动窗口通用优化策略

5.1 数据结构选择

根据字符集大小选择合适的数据结构：

• 小写字母：长度26的数组（最快）
• ASCII字符：长度128的数组
• Unicode字符：哈希表（如Python的defaultdict）

5.2 剪枝策略

1. 提前终止：当找到可行解且窗口已达最小可能大小时立即返回
2. 跳跃移动：当某些条件满足时，左指针可以跳跃移动而非逐步移动

5.3 调试技巧

1. 窗口可视化：打印每次移动后的窗口内容
2. 状态跟踪：记录左右指针位置和关键变量值
3. 边界测试：空字符串、单字符、全相同字符等特殊情况

# 调试示例 def debug_window(s, left, right): print(f"Window [{left}:{right}]: {s[left:right+1]}") print(f"Left: '{s[left]}', Right: '{s[right]}'")

6. 高频面试考点解析

6.1 变种问题集锦

1. 最长无重复子串：维护字符最后出现位置的哈希表
2. 字符串包含所有字符的最短子串：不考虑频次时的简化版
3. 最多K个不同字符的最长子串：维护字符种类计数器

6.2 白板编程注意事项

1. 先明确窗口移动条件
2. 处理好初始状态和边界条件
3. 注意循环不变量的维护

6.3 复杂度分析要点

1. 明确每个指针的移动次数
2. 考虑内部操作的时间成本（如哈希表操作）
3. 区分均摊复杂度和最坏复杂度

7. 工程实践中的性能对比

在实际编码中，不同实现方式性能差异显著。以76题为例：

实测建议：在面试中优先考虑可读性，在实际工程中再考虑微优化。