LeetCode 高频题：滑动窗口的复杂度证明与边界用例

LeetCode 高频题滑动窗口的复杂度证明与边界用例一、滑动窗口难点不在模板而在窗口定义滑动窗口是高频题型但很多错误解法都不是不会写双指针而是窗口含义没定义清楚。窗口里维护什么条件什么时候右扩什么时候左缩答案在扩前更新还是缩后更新这些都必须明确。模板背下来不难难的是知道模板为什么成立。以“最长无重复子串”为例窗口[left, right]表示当前不含重复字符的连续区间。右指针每次加入新字符如果出现重复就移动左指针直到重复消失。正确性来自一个不变量每轮循环结束后窗口内没有重复字符。如果不变量说不清代码很容易在边界上错。比如先更新答案再收缩窗口会把含重复字符的窗口算进去。或者左指针移动时只移动一步遇到多个重复时仍然错误。二、窗口状态变化不变量如何维持flowchart TD A[右指针加入字符] -- B{窗口是否满足约束} B -- 是 -- C[更新答案] B -- 否 -- D[移动左指针] D -- E[更新窗口计数] E -- B C -- F[处理下一个右指针]滑动窗口的本质是用两个单调移动的指针维护一个局部状态。右指针只向右左指针也只向右所以总移动次数不超过2n。这就是 O(n) 复杂度的来源而不是因为“看起来只有一个 for 循环”。窗口题常见两类。第一类是固定窗口比如长度为 k 的子数组最大平均值。第二类是不定窗口比如满足某个约束的最长/最短区间。不定窗口更需要写清楚收缩条件。三、代码实现最长无重复子串下面是一个可复现的 Python 实现。def length_of_longest_substring(s: str) - int: left 0 freq: dict[str, int] {} ans 0 for right, ch in enumerate(s): freq[ch] freq.get(ch, 0) 1 while freq[ch] 1: old s[left] freq[old] - 1 if freq[old] 0: del freq[old] left 1 ans max(ans, right - left 1) return ans这段代码的关键是while freq[ch] 1。它只关注新加入字符是否重复因为加入前窗口已经满足无重复不变量。收缩时不断移除左端字符直到新字符不重复为止。此时窗口重新满足条件才能更新答案。边界用例应该覆盖空串、全相同、全不同、重复在中间、重复在两端。assert length_of_longest_substring() 0 assert length_of_longest_substring(aaaa) 1 assert length_of_longest_substring(abcd) 4 assert length_of_longest_substring(abba) 2 assert length_of_longest_substring(pwwkew) 3四、权衡分析滑动窗口不是所有区间题的答案滑动窗口适合约束具有单调性的题。比如窗口变大后和只会变大字符计数只会增加。这样左指针收缩能让状态朝满足条件方向变化。如果约束不具备单调性滑动窗口就可能失效。例如包含负数的子数组和问题窗口和不再随右扩单调增加。此时用滑动窗口找最短满足区间就容易错需要前缀和、哈希表或单调队列。判断能不能用滑动窗口先看左指针移动是否一定能修复约束。空间复杂度也要说明。字符集固定时频率表空间可以视为 O(1)。如果字符集不固定空间是 O(min(n, 字符集大小))。题解里直接写 O(1) 可能不严谨。生产落地补充从能跑到可维护从生产落地角度看这类方案不能只停留在主流程。更关键的是把输入校验、失败分支、资源上限和回滚路径提前写清楚。主流程通常容易在演示环境里跑通真正暴露问题的是异常输入、依赖抖动、并发放大和权限边界。一篇技术方案如果没有解释这些约束读者很难判断它能否放进真实系统。评估时建议先定义三类指标正确性指标、稳定性指标和成本指标。正确性指标回答结果是否可信稳定性指标回答失败时是否可控成本指标回答持续运行是否划算。三类指标要同时进入验收清单不能只用平均耗时或单次成功率证明方案有效。异常路径补充把失败当成接口契约下面的补充片段强调一个原则调用方必须得到稳定、可解释的错误而不是在超时、空输入或依赖失败时收到模糊结果。代码不追求覆盖所有业务细节而是展示输入校验、超时控制和错误封装这三个生产系统最容易遗漏的环节。from __future__ import annotations import asyncio from dataclasses import dataclass dataclass class GuardedResult: ok: bool value: str error: str async def run_with_guard(input_text: str, timeout: float 3.0) - GuardedResult: if not input_text.strip(): return GuardedResult(okFalse, errorinput cannot be empty) try: async with asyncio.timeout(timeout): # 真实项目中这里放模型调用、数据库查询或外部服务请求。 await asyncio.sleep(0.01) return GuardedResult(okTrue, valuefaccepted: {input_text}) except TimeoutError: return GuardedResult(okFalse, erroroperation timeout) except Exception as exc: return GuardedResult(okFalse, errorfoperation failed: {exc})五、总结滑动窗口的核心是窗口定义和不变量。先明确窗口表示什么再写右扩、左缩和答案更新时机。复杂度 O(n) 来自左右指针都单调移动而不是来自代码长得像一层循环。做这类题时建议先写一句不变量再写边界测试。只背模板不够。模板能帮你起步不变量才能保证你不会在隐藏用例里翻车。