子串的滑动窗口
实现可变大小的滑动窗口，查找最长无重复字符子串，以及包含所有目标字符的最小窗口。
子串的滑动窗口 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
滑动窗口概念
滑动窗口维护由左指针和右指针界定的子数组（或子字符串）。与其从头开始以 O(n²) 的复杂度重新计算每个可能子数组的属性，不如通过向右扩展窗口来添加一个元素，并通过向左收缩窗口来移除一个元素，同时以每一步 O(1) 的复杂度维护运行状态。这样就能得到 O(n) 的算法。之所以称为“滑动”窗口，是因为它会在数组中向前移动，而不会向后移动。
# Fixed-size window sum: O(n) after O(k) setup
def max_sum_window(nums, k):
window_sum = sum(nums[:k]) # initial window
best = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] # add new right
window_sum -= nums[i - k] # remove old left
best = max(best, window_sum)
return best
print(max_sum_window([2,1,5,1,3,2], 3)) # 9 ([5,1,3])固定窗口大小与可变窗口大小
滑动窗口有两种形式。在固定大小窗口中，两个指针以相同的速度前进，窗口始终恰好包含 k 个元素。在可变大小窗口中，右指针会贪心地扩展，只有当窗口违反约束时，左指针才会收缩。可变大小窗口可以解决“无重复字符的最长子字符串”之类的问题，因为这类问题无法预先知道最优窗口大小。
# Variable window: longest substring with at most k distinct chars
def longest_k_distinct(s, k):
from collections import defaultdict
freq = defaultdict(int)
left = 0
best = 0
for right in range(len(s)):
freq[s[right]] += 1
while len(freq) > k: # window invalid: shrink
freq[s[left]] -= 1
if freq[s[left]] == 0:
del freq[s[left]]
left += 1
best = max(best, right - left + 1)
return best
print(longest_k_distinct('eceba', 2)) # 3 ('ece')
print(longest_k_distinct('aa', 1)) # 2无重复字符的最长子字符串
这是最经典的可变滑动窗口问题。请使用集合跟踪当前窗口中的字符。向右扩展；发现重复字符后，从左侧收缩窗口，直到移除该重复字符。更快的版本会使用哈希映射存储每个字符最近一次出现的索引，这样左指针就能一步跳过重复字符，而不必逐步向前移动。
def length_of_longest_substring(s):
char_idx = {} # char -> last seen index
left = 0
best = 0
for right, c in enumerate(s):
if c in char_idx and char_idx[c] >= left:
left = char_idx[c] + 1 # jump past duplicate
char_idx[c] = right
best = max(best, right - left + 1)
return best
print(length_of_longest_substring('abcabcbb')) # 3 ('abc')
print(length_of_longest_substring('bbbbb')) # 1
print(length_of_longest_substring('pwwkew')) # 3 ('wke')最小覆盖子字符串
给定字符串 s 和 t，请在 s 中找到包含 t 的全部字符的最小窗口。请使用两个频率映射：need（所需字符）和 have（当前窗口中满足要求的字符）。跟踪 t 中已经满足的不同字符数量（formed 计数器）。向右扩展以纳入字符；当 t 的全部字符都已覆盖时，向左收缩以使窗口最小化。时间复杂度为 O(|s| + |t|)。
from collections import Counter
def min_window(s, t):
if not t or not s: return ''
need = Counter(t)
have = {}
formed = 0
required = len(need)
left = 0
best = float('inf'), 0, 0
for right, c in enumerate(s):
have[c] = have.get(c, 0) + 1
if c in need and have[c] == need[c]:
formed += 1
while formed == required:
if right - left + 1 < best[0]:
best = right - left + 1, left, right
have[s[left]] -= 1
if s[left] in need and have[s[left]] < need[s[left]]:
formed -= 1
left += 1
return s[best[1]:best[2]+1] if best[0] != float('inf') else ''
print(min_window('ADOBECODEBANC', 'ABC')) # 'BANC'滑动窗口模板
大多数可变滑动窗口问题都遵循同一个模板：向右扩展以纳入新字符，更新窗口状态，检查有效性；如果窗口无效，就从左侧收缩，直到重新有效。关键在于，左指针只会向前移动，不会向后移动，因此所有收缩步骤的总工作量为 O(n)。每个元素在窗口中最多访问两次（一次加入，一次移除）。
def sliding_window_template(s, condition_check, update_state, remove_state):
"""
Generic sliding window skeleton.
Adapt condition_check, update_state, remove_state per problem.
"""
left = 0
state = {} # or whatever state you need
best = 0
for right in range(len(s)):
update_state(state, s[right]) # expand window
while not condition_check(state): # window invalid
remove_state(state, s[left]) # shrink window
left += 1
best = max(best, right - left + 1)
return best字符串中的排列
请检查模式 p 的任意排列是否作为子字符串存在于 s 中。排列检查等价于检查一个与 p 具有相同字符频率的窗口。请维护一个恰好包含 len(p) 个字符的滑动窗口，并比较频率计数。每一步比较完整的 Counter 对象需要 O(26) 的时间（对于小写英语字符来说这是常数），因此总体复杂度为 O(n × 26) = O(n)。
from collections import Counter
def check_inclusion(p, s):
if len(p) > len(s): return False
need = Counter(p)
window = Counter(s[:len(p)])
if need == window: return True
for right in range(len(p), len(s)):
left = right - len(p)
window[s[right]] += 1
window[s[left]] -= 1
if window[s[left]] == 0:
del window[s[left]]
if window == need:
return True
return False
print(check_inclusion('ab', 'eidbaooo')) # True ('ba')
print(check_inclusion('ab', 'eidboaoo')) # False异位词子字符串：统计全部
请找出 s 中 p 的所有异位词的起始索引。这与“字符串中的排列”使用相同的固定窗口技巧，但不是在首次匹配时返回真值，而是收集所有匹配位置。窗口大小固定为 len(p)；将窗口在 s 上滑动，并在每一步比较频率计数。
from collections import Counter
def find_anagrams(s, p):
result = []
need = Counter(p)
k = len(p)
window = Counter(s[:k])
if window == need:
result.append(0)
for right in range(k, len(s)):
window[s[right]] += 1
left_char = s[right - k]
window[left_char] -= 1
if window[left_char] == 0:
del window[left_char]
if window == need:
result.append(right - k + 1)
return result
print(find_anagrams('cbaebabacd', 'abc')) # [0, 6]至多含两种不同字符的最长子字符串
这是滑动窗口的一种变体：请找出包含至多 2 种不同字符的最长子字符串。维护当前窗口中字符的频率映射。当映射中的条目超过 2 个时，将左指针向右移动（减少频率，若频率为零则删除），直到恢复约束。这是“至多 k 种不同字符”问题在 k=2 时的特殊情况。
def longest_substring_two_distinct(s):
from collections import defaultdict
freq = defaultdict(int)
left = 0
best = 0
for right, c in enumerate(s):
freq[c] += 1
while len(freq) > 2:
freq[s[left]] -= 1
if freq[s[left]] == 0:
del freq[s[left]]
left += 1
best = max(best, right - left + 1)
return best
print(longest_substring_two_distinct('eceba')) # 3 ('ece')
print(longest_substring_two_distinct('ccaabbb')) # 5 ('aabbb')滑动窗口最大值
请找出每个大小为 k 的窗口中的最大值。使用蛮力方法检查每个窗口的最大值需要 O(n×k) 的时间。最优方法使用由索引组成的单调双端队列：维护一个递减队列，使队首始终是当前窗口最大值的索引。当索引离开窗口时，从队首移除它；当更大的元素进入时，从队尾移除较小的索引。总时间复杂度为 O(n)。
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # stores indices, decreasing values
result = []
for i, n in enumerate(nums):
# Remove indices outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Maintain decreasing order
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if i >= k - 1: # window is full
result.append(nums[dq[0]])
return result
print(max_sliding_window([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]何时使用滑动窗口
遇到以下情况时可以考虑使用滑动窗口：
- 带有约束的子字符串或子数组（最大长度、总和 = k、至多 k 种不同字符）
- 带有聚合操作的固定窗口大小（最大值、总和、频率）
- 连续范围问题（而不是任意子集）
# Recognising sliding window problems:
# 1. Fixed window: 'maximum average of subarray of length k'
def max_avg(nums, k):
s = sum(nums[:k])
best = s
for i in range(k, len(nums)):
s += nums[i] - nums[i-k]
best = max(best, s)
return best / k
print(max_avg([1,12,-5,-6,50,3], 4)) # 12.75
# 2. Variable window: 'smallest subarray with sum >= target'
def min_sub_len(target, nums):
left = s = 0
best = float('inf')
for right, n in enumerate(nums):
s += n
while s >= target:
best = min(best, right - left + 1)
s -= nums[left]; left += 1
return 0 if best == float('inf') else best
print(min_sub_len(7, [2,3,1,2,4,3])) # 2统计有效窗口：至多 K 个
有些问题要求统计满足某个条件的子数组数量。一个实用技巧是：先统计包含至多 k 种不同字符的子数组数量，再通过相减得到恰好 k 种：exactly(k) = at_most(k) - at_most(k-1)。每次调用“至多 k 种”函数都需要 O(n) 的时间，因此总复杂度仍为 O(n)。该函数通过累加 right - left + 1 来统计不同字符数量不超过 k 的窗口（对于每个 right，这表示所有有效的左端点）。
from collections import defaultdict
def subarrays_at_most_k(s, k):
freq = defaultdict(int)
left = 0
count = 0
for right, c in enumerate(s):
freq[c] += 1
while len(freq) > k:
freq[s[left]] -= 1
if freq[s[left]] == 0: del freq[s[left]]
left += 1
count += right - left + 1 # all valid windows ending at right
return count
def subarrays_exactly_k(s, k):
return subarrays_at_most_k(s, k) - subarrays_at_most_k(s, k-1)
print(subarrays_exactly_k('araaci', 2)) # 9快速检查
请测试您对本课数据结构与算法——编程面试准备相关概念的理解。
课程回顾
本课您学习了：滑动窗口通过维护一个运行中的窗口状态，并在元素进入和离开时以 O(1) 的时间更新状态，从而消除了 O(n²) 的复杂度；固定大小窗口以相同的速度推进两个指针，而可变大小窗口会贪心地向右扩展，只有在违反约束时才向左收缩；以及最小覆盖子字符串和字符串中的排列都使用带有频率映射的窗口状态，并通过计数器跟踪当前满足要求的字符数量。接下来我们将学习异位词和字符频率映射。
常见问题解答
「子串的滑动窗口」课时是免费的吗？
是的 — 「子串的滑动窗口」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「子串的滑动窗口」这节课中我会学到什么？
实现可变大小的滑动窗口，查找最长无重复字符子串，以及包含所有目标字符的最小窗口。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「子串的滑动窗口」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。