想象你坐上一列缓缓行驶的绿皮火车，靠窗而坐。窗框是固定的，但窗外的山峦、田野、村庄在眼前一一流过。你不需要把头探出车外去“扫描”整个世界，只需要盯住这扇窗——每一刻看到的风景，就是当前窗口的内容。火车前进一小步，窗口内的景色就更新一小步：旧的山退出去，新的树走进来。这就是滑动窗口的底层直觉：用一个大小可控的观察框，沿着数据流滑动，每次只处理“新进来”和“流出去”的那部分信息，而不是把整片风景重新看一遍。 在算法面试中，滑动窗口是解决“子数组/子串”类问题的利器。很多看起来需要双重循环的暴力题（比如“和大于等于某个值的最短子数组”“最长无重复字符的子串”），一旦套上滑动窗口的思维，时间复杂度直接从 O(n²) 降到 O(n)。本文用一列火车的旅程，带你从零掌握这个看似简单却又极其深刻的核心策略。

岗位关联

对 AI 从业者来说，滑动窗口是算法面试的基础必修课。面试中它是高频考点，工作中它是数据流处理、序列分析、特征窗口聚合的重要基石，值得系统掌握。

目录
  1. 可视化演示
  2. 核心原理
  3. 经典题型
  4. 解题模板
  5. 边界条件
  6. 复杂度分析
  7. 实战技巧
  8. AI 应用场景
  9. Python 演示
  10. 常见误区
  11. 面试题

可视化演示

展示双指针窗口原理、定长窗口增量更新、变长窗口条件收缩。切换模式理解滑动窗口面试核心策略与解题套路。

本节配有交互动效（进入视口后自动加载，约 3KB）。

滑动窗口核心原理 双指针维护动态区间：右指针扩张窗口纳入新元素，左指针收缩窗口移除旧元素 一次遍历完成所有窗口操作，时间复杂度O(n)，避免暴力枚举的O(n²) while right < n: expand(right); while invalid: shrink(left) 双指针框架是滑动窗口的基础

核心原理

火车继续向前，你发现一个有趣的现象：窗框大小不变，但窗外的风景每次只“更新”一小段——车尾方向退出一座塔，车头方向进入一片稻田。你不需要把整条山脉重新看一遍，只需要盯着“新进来”和“退出去”的两个局部变化。滑动窗口的核心思想正是如此：在一个连续序列上维护一个子区间，每次移动时只处理边界处的增量变化，而不是重建整个区间的状态。

将“火车窗框”映射到算法中，窗口就是数组或字符串上的一个连续子区间，用两个索引标记：左边界 l 和右边界 r。右边界负责“引入新风景”（加入新元素），左边界负责“放走旧风景”（移除多余元素）。当我们需要在序列上寻找满足某种条件的最短、最长或包含特定模式的子区间时，双指针就像火车的两扇窗沿，框住我们要观察的连续片段。

滑动窗口的精髓在于状态复用：每次向右移动一步，窗口的内容只改变两个位置——最右边新进一个元素，最左边可能走掉一个元素。只要维护一个“当前窗口状态”变量（如区间和、字符频次表），每次移动最多只需两次更新操作，就能在常数时间内得到新窗口的状态，这从根本上避免了暴力重新计算的高昂代价。

回到火车的比喻：正是因为每一帧风景只在上一步的基础上换掉“头尾”两个片段，你才能悠闲地坐在窗边看完整座山，而不是每次都从头站起身把整条风景线重新扫描一遍。滑动窗口的优雅之处，正在于它把“重新认识世界”变成“只关注变化”。

state(l,r)=state(l,r−1)+add(nums[r])−remove(nums[l])\text{state}(l, r) = \text{state}(l, r-1) + \text{add}(\text{nums}[r]) - \text{remove}(\text{nums}[l])
公式通俗说明：窗口状态的变化 = 原状态 + 右边界新元素的贡献 − 左边界流出元素的负贡献。就像火车窗外的风景＝上一刻的风景＋右侧新出现的塔－左侧消失的树。
  1. 右边界扩张（加入新元素）当右指针从 r−1 移动到 r 时，新元素 nums[r] 进入窗口，窗口状态从 state(l, r−1) 变为 state(l, r)。这一步在固定窗口模板中对应“每次循环 right++ 并纳入新值”。
    state(l,r)=state(l,r−1)+nums[r]\text{state}(l, r) = \text{state}(l, r-1) + \text{nums}[r]
  2. 左边界收缩（移除旧元素）当左指针从 l 移动到 l+1 时，旧元素 nums[l] 离开窗口，状态需要减去它的贡献。这一步在可变窗口模板中对应“while 条件不满足时 left++”。
    state(l+1,r)=state(l,r)−nums[l]\text{state}(l+1, r) = \text{state}(l, r) - \text{nums}[l]
  3. 常数时间更新由于每一步只做一次加法或减法，窗口的移动成本是 O(1)，整个滑过序列的总成本为 O(n)，而不需要像暴力解法那样对每个子区间重新求值。
    T(n)=O(n),每个元素最多进出窗口各一次T(n) = O(n), \quad \text{每个元素最多进出窗口各一次}

经典题型

掌握了滑动窗口的底层直觉，我们来看看面试中最常出现的四类题型。它们就像火车沿途的四个站点，虽然风景各异，但到达方式完全一致——都是同一列“滑动窗口号”列车。第一站是最长无重复子串：找出字符串中最长的不含重复字符的子串长度，这是可变窗口的典型代表。第二站是最小覆盖子串：在字符串 S 中找到包含字符串 T 全部字符的最短子串，这是“满足条件最短”类问题的经典模板。第三站是最小长度子数组：找到和 ≥ target 的最短连续子数组。第四站是字符串异位词：判断一个字符串的某个排列是否出现在另一个字符串中，这是固定窗口的教科书级应用。

每个站点都有标尺式的公式。以最长无重复子串为例，核心就是“每次右指针向前，左指针跳到重复字符的下一个位置”：

其中窗口满足“无重复”约束，l 是窗口左端，r 是当前右端。窗口中每个字符在哈希表中记录的频次均为 1。

如果说最长无重复子串是“窗口里不要出现重复的风景”，那么最小覆盖子串就是“窗口里必须集齐所有指定的风景”。最小长度子数组则是“窗口累加值够了就赶紧收窄”。字符串异位词则要求“窗口里每个风景出现的次数必须分毫不差”。这四个站点的底层机制一致——右指针扩展、左指针收缩、中间维护状态——理解了这个共同框架，题目变化就万变不离其宗。

ans=max⁡(ans, r−l+1)\text{ans} = \max(\text{ans}, \ r - l + 1)
公式通俗说明：答案永远取“当前窗口宽度”的最大值。就像你记录全程车窗里看到的风景种类最大值——只要窗口内没有重复的“风景”，宽度就是有效候选。
  1. 右指针扫描移动右指针 r 遍历整个字符串，将新字符 s[r] 的频次 +1。
    freq[s[r]]+=1\text{freq}[s[r]] \mathrel{+}= 1
  2. 检测重复并收缩如果频次 >1，说明窗口内有重复字符，需要左指针 l 不断右移，直到频次回到 1，同时沿途移除左边界字符的频次。
    while(freq[s[l]]>1): freq[s[l]]−=1, l+=1\text{while}(\text{freq}[s[l]] > 1): \ \text{freq}[s[l]] \mathrel{-}= 1,\ l \mathrel{+}= 1
  3. 更新答案窗口满足约束后，用当前窗口宽度 r−l+1 更新最大值。整个过程每个字符最多被左右指针各访问一次，总复杂度 O(n)。
    ans=max⁡(ans, r−l+1)\text{ans} = \max(\text{ans}, \ r - l + 1)

解题模板

每一列火车都有标准驾驶室：仪表盘（状态变量）、油门（右指针）、刹车（左指针）、时刻表（答案更新）。滑动窗口的解题模板也是如此——不管题目的包装多么花哨，核心流程永远是一致的四步。先把模板背熟，然后根据题目条件替换其中的“判断逻辑”和“更新逻辑”。

模板的骨架可以概括为：初始化左右指针和状态变量 → 右指针逐位扩展，引入新元素并更新状态 → 当窗口不再满足约束条件（或满足收缩条件）时，左指针向右收缩，同时反向更新状态 → 在合适的时机（扩展后或收缩后）更新答案。这个框架适用于所有滑动窗口题目，区别只在于“何时收缩”和“何时更新答案”。

一句话总结这个模板：右指针是油门，负责往前冲；左指针是刹车，负责保持窗口有效；答案更新就是记录沿途最美风景。当你面对一道滑动窗口题时，先在纸上写下这四步，再填充具体条件，就不会在考场上手忙脚乱了。

while r<n:expand(r);while condition_broken: shrink(l);update(ans)\text{while } r < n: \quad \text{expand}(r); \quad \text{while } \text{condition\_broken}: \ \text{shrink}(l); \quad \text{update}(\text{ans})
公式通俗说明：右指针冲到数组尽头之前，不停执行“扩展→必要时收缩→更新答案”的循环。就像火车司机：车没到站就持续加油门，窗户太挤就放下一点窗沿，并且每时每刻记录最漂亮的风景。
  1. 初始化左指针 l=0，右指针 r=0，状态变量（如窗口和、频次表）置空。
    l=0,r=0,state=∅l = 0, \quad r = 0, \quad \text{state} = \varnothing
  2. 右边界扩张每轮循环中 r 右移一位，把新元素纳入状态。这一步保证每个元素都会进入窗口一次。
    state.add(nums[r]);r+=1\text{state.add}(\text{nums}[r]); \quad r \mathrel{+}= 1
  3. 条件收缩（左边界）当窗口状态不满足问题约束（例如窗口出现重复、和超过 target），左指针持续右移并撤销旧元素的贡献，直到重新满足约束。
    while ¬valid(state): state.remove(nums[l]); l+=1\text{while } \neg\text{valid}(\text{state}): \ \text{state.remove}(\text{nums}[l]); \ l \mathrel{+}= 1
  4. 更新答案在收缩完成后（或扩展后，取决于题目），根据当前窗口计算并更新最优解。
    ans=max⁡(ans, r−l+1) 或 ans=min⁡(ans, r−l)\text{ans} = \max(\text{ans}, \ r - l + 1) \ \text{或} \ \text{ans} = \min(\text{ans}, \ r - l)

边界条件

火车行驶中总会遇到隧道、临时停靠、空车厢等特殊情况——算法面试题也不例外。边界条件处理是区分“背模板”和“真懂”的分水岭。滑动窗口题目最容易踩的坑集中在四个场景。

第一个场景是空输入：如果数组或字符串为空，任何窗口都不存在，答案应直接返回 0 或空串；同时若目标值不存在，也要提前判断。第二个场景是窗口越界：当右指针到达序列末尾时，循环必须终止；当左指针超过右指针时（窗口为空），状态变量要能正确重置。第三个场景是单元素窗口：数组只有一个元素时，窗口最大宽度为 1，循环和收缩逻辑必须保证 l ≤ r 始终成立。第四个场景是全同字符：如 "aaaaa" 或 [1,1,1,1]，此时每次扩展都会触发收缩，要确保没有死循环或重复计算。

边界条件是面试中“无声的加分项”。主动写出空输入判断和指针合法性检查，就像老司机上车先系安全带——面试官一眼就能看出你的工程素养。许多考生在 LeetCode 上“通过”了题目，却在白板面试中超时，正是因为边界处理不到位导致 bug 难以排查。

边界检查：if n=0⇒return 0;if l>r⇒state reset\text{边界检查：} \quad \text{if } n = 0 \Rightarrow \text{return 0}; \quad \text{if } l > r \Rightarrow \text{state reset}
公式通俗说明：开车前检查油箱（空输入），行驶中看后视镜（越界），拐弯时确认车轮没悬空（指针关系），全程保持均匀速度（全同字符）。
  1. 空输入特判长度为 0 时返回 0，避免访问 nums[0] 造成越界错误。
    if n=0: return 0\text{if } n = 0: \ \text{return } 0
  2. 指针合法性收缩时确保 l ≤ r，若 l 超过 r 说明窗口为空，应重置状态。
    if l>r: state=∅, l=r\text{if } l > r: \ \text{state} = \varnothing, \ l = r
  3. 更新顺序保证在右指针扩展前先检查 r < n，在左指针收缩前检查 l < r，确保指针永不越界。
    while r<n and condition: …\text{while } r < n \ \text{and} \ \text{condition}: \ \dots

复杂度分析

为什么滑动窗口在面试中如此受宠？答案藏在复杂度分析里。暴力解法解决“满足条件的子数组”类问题时，通常需要枚举所有 O(n²) 个子区间，并对每个区间求和或检查条件，导致 O(n²) 甚至 O(n³) 的总复杂度。而滑动窗口利用“状态复用”这一核心思想，让每个元素最多被左右指针各经过一次，从而将均摊复杂度压缩到 O(n)。

更精确地说，在完整的滑动过程中，右指针从 0 扫到 n−1，左指针也从 0 单调推进到 n−1（或某个上限）。两套指针各自最多移动 n 步，因此总操作数为 O(2n) = O(n)。空间复杂度方面，如果只维护一个整数变量（如窗口和），额外空间是 O(1)；如果需要维护频次表（如记录字符出现次数），则是 O(k)，其中 k 是字符集大小（如 26 或 128），通常视为常数。

面试时，如果你能主动说出时间和空间复杂度，并解释“每个元素最多进出窗口各一次”的均摊依据，面试官会立刻对你刮目相看。这个分析也不仅仅是考试技巧——在 AI 工程中处理序列数据时，O(n) 和 O(n²) 在百万级数据规模下可能意味着一毫秒和一小时的巨大差距。

T(n)=O(n),S(n)=O(1) 或 O(k)T(n) = O(n), \quad S(n) = O(1) \ \text{或} \ O(k)
公式通俗说明：时间上，每个元素最多“进窗一次、出窗一次”，就像每片风景只在你的视野中出现过一次；空间上，你只需要记住窗口内的信息，不用把整条铁路沿线的风景都装进背包。
  1. 右指针移动次数右指针从 0 遍历到 n−1，恰好 n 次。
    ∑r=0n−11=n\sum_{r=0}^{n-1} 1 = n
  2. 左指针移动次数左指针最多也移动 n 次（每次 while 收缩 l++）。
    ∑l=0n−11=n\sum_{l=0}^{n-1} 1 = n
  3. 总操作数两边操作累加得 2n，忽略常数后为 O(n)。
    T(n)=n+n=O(n)T(n) = n + n = O(n)

实战技巧

当你能熟练运用模板之后，还有一些“老司机”才知道的实战技巧，能让你在面试中游刃有余。第一个技巧是用哈希表（字典）记录窗口内字符频次。处理最长无重复子串时，哈希表能 O(1) 地判断字符是否重复；在处理最小覆盖子串时，还能快速判断窗口是否包含目标字符集。

第二个技巧是用数组替代字典。当字符集是有限的已知集合（如英文字母 a-z）时，用长度为 26 的 int 数组而非字典，可以将空间开销降到最低，同时避免哈希碰撞的开销。第三个技巧是避免重复计算——滑动窗口本身就是避免重复计算的艺术，但要注意不要在收缩和扩展时反复调用求窗口和的函数，也不要在循环内频繁查询不必要的信息。

最后一个技巧是双指针时机的协同控制——清楚“什么时候该收缩左边界”比“如何收缩”更重要。固定窗口通常每步右指针移动后就移动左指针；可变窗口则等到窗口不满足条件才收缩。掌握这些技巧，你在面试中不仅能写出正确的解，还能写出让面试官眼前一亮的优雅解。

优化： 用数组 cnt[26] 替代 dict,count-update O(1)\text{优化：} \ \text{用数组} \ \text{cnt}[26] \ \text{替代} \ \text{dict}, \quad \text{count-update} \ O(1)
公式通俗说明：与其每次问“窗外有没有一只白鹭”（查字典），不如预先准备 26 个观察位（数组），每个位子记录对应鸟种的数量，看一眼就知道。
  1. 哈希表记录频次用 dict 映射字符 → 出现次数，每次窗口移动时更新两个字符的频次。
    freq[c]=freq.get(c,0)+1\text{freq}[c] = \text{freq.get}(c, 0) + 1
  2. 数组代替字典如果元素是有限集合（如字母、数字 0-9），用定长数组下标直接索引。
    cnt[c−′a′]+=1(c∈[a,z])\text{cnt}[c - 'a'] \mathrel{+}= 1 \quad (c \in [a, z])
  3. 滑动过程零额外扫描整个算法只依赖左右指针的增量更新，不引入任何内层循环或重复计算。
    while r<n: cnt[nums[r]]+=1; …\text{while } r < n: \ \text{cnt}[\text{nums}[r]] \mathrel{+}= 1; \ \dots

AI 应用场景

场景一：实时网络流量监控中的固定窗口聚合

阶段：数据预处理与特征工程

解决的问题：传统监控系统需要不断重新扫描所有数据包以计算某个时间窗口内的平均流量或异常指标，数据量大时开销巨大。滑动窗口技术让系统每到一个新数据包只做一次“加入新值、移除旧值”的增量计算，实时完成滚动均值和峰值检测。

具体案例：某安全团队监控每秒到达的流量数据，需要计算“过去60秒内平均流量是否超过阈值”。如果每次新数据到达都重算 60 秒区间内的数据，成本极高；用固定窗口加增量求和，每来一个新数据点只需一次加法和一次减法，即可实时获取滑动均值，一旦超过阈值立即触发告警。这正是异常检测系统 DDoS 攻击识别的基础技术。

场景二：自然语言处理中的 n-gram 特征统计与匹配

阶段：文本特征提取与模式匹配

解决的问题：在文本分类、机器翻译等 NLP 任务中，经常需要提取固定长度的 n-gram 特征或判断某个短语是否出现在长文本中。滑动窗口可以快速完成所有连续 n-gram 的频次统计，而不必为每个位置单独创建子串。

具体案例：在构建垃圾邮件分类器时，需要统计邮件正文中所有长度为 3 的连续字符组合（trigram）的频次。用滑动窗口遍历邮件文本，每步只移入和移出一个字符即可更新整个窗口内容，从而高效构建 TF-IDF 向量，提升分类模型的训练效率。

场景三：时序数据滑动平均与趋势预测特征构造

阶段：特征工程

解决的问题：训练股票预测或传感器故障预测模型时，经常需要构造滚动窗口的统计特征（移动平均、滚动标准差等）。传统实现的高复杂度会拖慢特征工程管线；滑动窗口用“增量更新”实现了从 O(n×k) 到 O(n) 的性能飞跃。

具体案例：一家制造业公司需要基于传感器的振动数据预测设备故障。他们为每台设备构造了过去 10 个时间点的滚动均值和滚动方差作为特征。借助滑动窗口增量算法，在生产环境中只需 O(1) 时间更新每个新时间步的特征值，支撑了大规模实时预测系统的运行。

Python 演示

python59 行
def min_subarray_len(target, nums):    """和 >= target 的最短连续子数组长度（滑动窗口版）    使用可变窗口：右指针扩展，左指针收缩    """    n = len(nums)    left = 0    total = 0    best = n + 1    for right in range(n):        total += nums[right]        while total >= target:            best = min(best, right - left + 1)            total -= nums[left]            left += 1    return best if best <= n else 0  def length_of_longest_substring(s):    """最长无重复字符子串长度（可变窗口版）"""    freq = {}    left = 0    ans = 0    for right, ch in enumerate(s):        freq[ch] = freq.get(ch, 0) + 1        while freq[ch] > 1:            freq[s[left]] -= 1            left += 1        ans = max(ans, right - left + 1)    return ans  def find_anagrams(s, p):    """找到 s 中 p 的所有异位词起始下标（固定窗口版）"""    n, m = len(s), len(p)    if n < m:        return []    target = [0] * 26    window = [0] * 26    for ch in p:        target[ord(ch) - ord('a')] += 1    res = []    for i in range(n):        window[ord(s[i]) - ord('a')] += 1        if i >= m:            window[ord(s[i - m]) - ord('a')] -= 1        if window == target:            res.append(i - m + 1)    return res  if __name__ == "__main__":    nums = [2, 3, 1, 2, 4, 3]    print("min_subarray_len(7, [2,3,1,2,4,3]) =", min_subarray_len(7, nums))     s = "abcabcbb"    print("length_of_longest_substring('abcabcbb') =", length_of_longest_substring(s))     s2, p2 = "cbaebabacd", "abc"    print("find_anagrams('cbaebabacd', 'abc') =", find_anagrams(s2, p2))
目的：演示滑动窗口的三大核心场景——可变窗口求最短、可变窗口求最长、固定窗口找异位词。三个函数覆盖了最常见的题型，可直接在本地环境运行验证。
  1. total += nums[right]右指针扩张，新元素进入窗口
  2. while total >= target:条件满足后，尝试收缩左边界
  3. best = min(best, right - left + 1)收缩前记录当前最短窗口
  4. freq[ch] = freq.get(ch, 0) + 1用哈希表维护窗口内字符频次
  5. while freq[ch] > 1:检测到重复字符时收缩窗口
  6. window[ord(s[i]) - ord('a')] += 1用定长数组替代字典，O(1) 更新
  7. if i >= m:窗口大小超过 m 后，每次移除最左侧字符
  8. if window == target:直接比较两个计数数组，判断异位词

常见误区

误区滑动窗口的“窗口”意思就是大小固定不变，所以只能解决“长度固定为 k”的问题。可变窗口的题掌握不了。

正解滑动窗口的核心是“左右双指针维护一个连续区间”，窗口既可以固定大小（如异位词判断），也可以动态伸缩（如最短子数组、最长无重复子串）。可变窗口的本质是：在保持“窗口有效”的前提下尽量大或尽量小，收缩时机由题目条件决定。就像火车的窗户可以拉宽、也可以收窄，窗框不是死的。

为何常见：初学者最先接触的往往是“固定窗口求最大均值”这类直观题目，容易把“窗口大小”理解为固定常数，忽略了滑动窗口更强大的可变骨架。

误区“反正最后要记录最值，收缩时看一眼就行，不用管收缩过程中窗口的变化。”一些人在更新答案时只在右指针扩展后记录，忽视了收缩过程中的有效窗口也是候选答案。

正解在“最短”类问题中，答案往往在收缩即将越界前的那一步产生；在“最长”类问题中，答案在收缩完成后记录。何时更新答案取决于题目问的是最长还是最短。务必想清楚“哪个时机的窗口才是合法候选”，再决定更新位置，否则会漏解。

为何常见：模板只写了四行伪代码，没有强调“更新答案的时机因题而异”，导致考生生搬硬套，在错误的位置取最值。

误区“外层 while 右指针，内层 while 左指针，这不是双重循环吗？时间复杂度肯定是 O(n²)。”

正解虽然代码上有两层循环，但左指针在整体过程中是单调递增的，最多移动 n 次；右指针也单调移动 n 次。两个指针的移动次数是相加关系（2n），不是嵌套乘积关系（n²）。这就是“均摊分析”——虽然单次操作可能触发多次收缩，但总收缩次数不超过 n。因此滑动窗口的总复杂度是 O(n)。

为何常见：许多人对“双重循环必为 O(n²)”有思维定式，忽略了两层循环的指针总移动量相加这一关键事实。

误区“字符串就是由 26 个小写字母组成的，用 26 长度的数组就够了，不用想太多。”

正解题目如果声明“只含小写英文字母”，用 26 长度的数组没问题；但若输入可能包含大写字母、数字、空格或 Unicode 字符，固定数组就会越界。此时应使用哈希表（字典）或根据字符范围动态确定数组大小。面试中要主动和面试官确认输入字符集，再决定用哪种数据结构。

为何常见：力扣上很多经典题默认小写字母，练习时的惯性思维带到了所有场景，忽略真实工程中字符集的多样性。

面试题

Q1. 滑动窗口在绝大多数问题中的时间复杂度是？

单选题 · easy

  • A.O(n²)，窗口每移动一步都需要重新扫描全区间
  • B.O(n)，每个元素最多进出窗口各一次且均摊线性← 正确答案
  • C.O(n³)，需要枚举所有子区间并逐一进行验证
  • D.O(logn)，因为使用了二分搜索技术来加速窗口滑动

答案：B。正确答案为 B。滑动窗口的右指针和左指针各自从起点单调走到终点，总移动次数约为 2n，均摊后为 O(n)。A 是暴力枚举的复杂度；C 是更差的暴力；D 中二分搜索不是滑动窗口的时间复杂度。

Q2. 以下哪个问题最适合用滑动窗口求解？

单选题 · easy

  • A.在无序数组中寻找第 k 大的元素
  • B.在字符串中寻找最长无重复字符的子串← 正确答案
  • C.对数组进行快速排序并输出有序序列
  • D.求两棵二叉树之间的最大公共祖先

答案：B。B 是典型的可变窗口问题，右指针扩展、左指针收缩以维持无重复条件。A 适合快速选择算法或堆，C 适合排序算法，D 是树上的递归搜索问题，均不适合滑动窗口。

Q3. 在“最长无重复子串”中，发现 s[right] 重复时，正确的操作是？

单选题 · mid

  • A.直接把左指针跳到 right 的位置，因为前面的窗口已经无效
  • B.左指针逐步右移并减少频次，直到窗口内不再包含重复字符← 正确答案
  • C.清空整个窗口并重置所有频次，从 right 重新开始计算无重复
  • D.将答案减一再继续扫描，避免重复字符导致的长度溢出问题

答案：B。正确答案是 B。当字符重复时，需要收缩左边界并逐位减少出去的字符频次，直到重复字符的频次降回 1。直接跳到 right 可能丢失最优解；清空窗口是暴力思路，丧失了滑动窗口的增量优势。

Q4. 滑动窗口能实现 O(n) 复杂度的根本原因是什么？

单选题 · mid

  • A.每次窗口移动时重新计算窗口内的所有元素总和与最大值
  • B.左右指针均单调移动且状态通过增量更新实现复用旧结果← 正确答案
  • C.利用哈希表在常数时间内找到每一个元素的下标位置信息
  • D.通过预处理前缀和数组来快速查询任意区间的通配符信息

答案：B。B 是核心原因。左指针和右指针各自单调移动，总移动次数为 2n，且每次移动只对状态做加减更新，因此是 O(n)。A 是暴力法，C 是哈希表的应用场景但非根本原因，D 说反了——前缀和可求解，但滑动窗口靠的是增量复用。

Q5. 对于“最小覆盖子串”问题，下列哪些说法是正确的？

多选题 · mid

  • A.当窗口已包含 T 的全部字符时，尝试收缩左边界以缩小窗口← 正确答案
  • B.每次右指针扩展后立即记录当前答案，即可得到最短子串长度
  • C.用频次表记录 T 和窗口字符，比较两者就能判断是否覆盖← 正确答案
  • D.窗口的右指针不需要遍历完整个字符串，可以提前终止扫描

答案：AC。A 正确——覆盖条件满足后收缩左边界是寻找最小解的必经之路。C 正确地描述了覆盖判断的方法。B 错误，因为只在扩展后记录答案可能错过收缩后的更短窗口；D 错误，右指针必须扫完整个字符串才能保证不遗漏更短的覆盖子串。

Q6. 固定窗口大小为 k 的滑动中，每移动一步需要完成的操作是？

单选题 · mid

  • A.对窗口内全部 k 个元素重新累加求和，确保窗口数据的准确性
  • B.将新的右元素加入窗口和，同时减去左边界流出元素的贡献量← 正确答案
  • C.将窗口大小翻倍再减半，以平衡数据结构内部存储的复杂度
  • D.对窗口内所有元素排序，保证下一步移动基于有序的序列数据

答案：B。B 是滑动窗口的增量维护方式——加入新元素、移除旧元素各一次，状态更新为 O(1)。A 是暴力做法，C 与窗口移动无关，D 每步排序会让复杂度退化为 O(k log k)。

Q7. 在可变窗口求“和 ≥ target 的最短子数组”中，为何 while 收缩能保证正确性？

单选题 · hard

  • A.因为收缩到不满足条件时，当前窗口的长度就是对答案的最大贡献
  • B.因为每个左边界只需匹配一个临界右边界，收缩不会遗漏更优解← 正确答案
  • C.因为左指针每步都跳转两个位置，有效缩小搜索范围到对数量级
  • D.因为收缩过程中只需要考虑偶数字数组，跳过所有奇数长度的区间

答案：B。B 正确。当右指针固定时，左指针一旦继续右移窗口将不再满足条件，因此以当前左边界为起点的最短有效子数组已经取到；后续左边界在新右指针条件下再找新答案。这种“单调性”保证了不会遗漏任何最优窗口。A 说法不通，C 和 D 是不存在的假设。

Q8. 关于滑动窗口的空间复杂度，下列说法正确的有哪些？

多选题 · hard

  • A.仅维护窗口和时，额外空间复杂度为 O(1)← 正确答案
  • B.使用 26 长度数组记录字母频次时，空间复杂度为 O(1)← 正确答案
  • C.使用哈希表记录任意字符频次时，空间复杂度为 O(k)← 正确答案
  • D.使用前缀和数组预处理时，空间复杂度可以降为 O(1)

答案：ABC。A、B 都正确，固定大小的额外空间视为 O(1)。C 正确，若字符集为 k 种，哈希表占用 O(k) 空间。D 错误——前缀和数组需要 O(n) 空间，并且在滑动窗口场景中通常并非必要。

Q9. 滑动窗口适用于什么问题场景的最主要特征？

单选题 · easy

  • A.求一个固定坐标点的最短路径或最长路径的算法问题场景
  • B.求连续子区间且子区间状态能通过边界增量更新的场景← 正确答案
  • C.在离散点集中找出所有点的凸包或最小包围圆的问题场景
  • D.在图中找到所有节点之间的最短路径并输出完整路径集合

答案：B。B 是滑动窗口的适用条件——连续区间、增量更新、单调移动。A 是图搜索问题，C 是计算几何问题，D 是图论最短路问题，都与滑动窗口无关。

Q10. 在进行滑动窗口边界条件检查时，以下哪些做法是有必要的？

多选题 · mid

  • A.输入为空时提前返回默认值，避免访问不存在的第一个元素← 正确答案
  • B.在收缩左指针前检查 l ≤ r，防止窗口变为空无效区间的错误← 正确答案
  • C.右指针到达数组末尾后仍继续循环，多处理一次边界处的数据
  • D.针对全同字符输入进行测试，确保收缩逻辑不会落入死循环← 正确答案

答案：ABD。A（空输入）、B（指针合法性）、D（全同字符特例）都是必要的边界防御。C 错误——右指针到达 n 后应终止循环，继续处理越界数据会让数组越界访问，属于常见的边界 bug。