滑动窗口
从边界移动，到状态维护

01LeetCode 3无重复字符的最长子串

核心知识点：集合、哈希表、可变窗口、左边界单调性

题意与约束

给定字符串 s，返回不含重复字符的最长连续子串的长度。字符可以是字母、数字、符号和空格；原题允许空串，长度至多 10⁵。不能仅用 26 位小写字母数组。

示例：s = "abcabcbb" → 3，最长之一为 "abc"；"bbbbb" → 1；"pwwkew" → 3，"wke" 连续，而 "pwke" 只是子序列。

解法一：集合 + 非法时收缩（基础主解）

不变量：每轮结束，集合恰好包含 s[left:right+1] 中的字符，并且没有重复。加入 ch 前，若它已在集合中，依次删除左端字符，直到旧 ch 被移出；然后加入当前 ch，更新最长长度。

1. left 与 best 从 0 开始，集合为空。
2. 枚举 right, ch，用 while 删除左端，保证当前 ch 可以安全加入。
3. 恢复合法后计算长度。最长答案记录在这一时刻。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        seen = set()
        left = 0
        best = 0
        for right, ch in enumerate(s):
            while ch in seen:
                seen.remove(s[left])
                left += 1
            seen.add(ch)
            best = max(best, right - left + 1)
        return best

关键代码解释与正确性

while ch in seen 必须重复执行。例如 "abba" 的第二个 b 到来时，先移出 a 仍然重复，还要移出旧 b。由于原窗口无重复，冲突只可能来自新字符；删除到旧字符之后就恢复了不变量。

固定 right 时，算法保留最靠左的合法起点，因此得到以 right 结尾的最长合法子串。被删掉的起点含重复字符，继续扩张也无法修复；遍历所有 right 后，最长答案不会遗漏。

示例推演：s = "abba"

时间复杂度：O(n)，每个字符进入与移出各至多一次。空间复杂度：O(min(n, Σ)) 辅助空间，返回整数为 O(1)。

解法二：记录最后位置，一步跳转左边界

last[ch] 保存该字符最近一次出现的下标。若旧下标在窗口内，left 跳到它后一位；若旧下标在窗口外，不需要移动。用 max 统一两种情况，再更新最后位置。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        last = {}
        left = 0
        best = 0
        for right, ch in enumerate(s):
            left = max(left, last.get(ch, -1) + 1)
            last[ch] = right
            best = max(best, right - left + 1)
        return best

关键代码：last.get(ch, -1) + 1 对首次出现的字符得到 0；max(left, ...) 防止左边界倒退。必须先读旧位置，再写入 right。

独立推演："abba" 在 right=2 时读到 last[b]=1，left 从 0 跳到 2；right=3 时 last[a]=0，取 max(2,1)=2，得到 "ba"。若不取 max，会错误把 "bba" 算作长度 3。

正确性与复杂度：旧字符位置之后是排除这次冲突的最早起点，max 保留此前冲突的约束，因此窗口始终是以 right 结尾的最长合法窗口。时间 O(n)，辅助空间 O(min(n,Σ))。

易错点与边界检查

• 使用 if 代替 while，会在 "abba" 中留下重复。
• 更新答案必须在窗口恢复合法之后；长度需要 +1。
• 最后位置字典允许保留窗口外的历史，不代表当前窗口成员集合。
• 空串返回 0；单字符返回 1；全相同返回 1；"a b!" 返回 4，空格也计入。

02LeetCode 438找到字符串中所有字母异位词

核心知识点：定长窗口、26 位计数、差分数组、不相等种类数

题意与约束

找到 s 中所有长度为 |p|、字符频次与 p 完全一致的连续子串，返回起始下标。异位词允许顺序不同，重复字符的数量必须一致。原题 s、p 均只含小写字母，长度 1 到 3×10⁴。

示例：s="cbaebabacd", p="abc" → [0,6]，对应 "cba" 与 "bac"；s="abab", p="ab" → [0,1,2]，窗口可以重叠。

解法一：定长窗口 + 26 位频次数组（主解）

不变量：处理完当前 right 后，window 记录以 right 结尾、长度不超过 m=|p| 的后缀频次。当长度超过 m，就移出一个最左字符。只有长度恰好 m 时，频次数组相等才代表异位词。

1. 把 p 计入 need，字符下标为 ord(ch)-ord('a')。
2. 加入 s[right]；若 right≥m，移出 s[right-m]。
3. right≥m-1 且 window==need 时，记录 right-m+1。

from typing import List

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        n, m = len(s), len(p)
        if m == 0 or m > n:
            return []
        need = [0] * 26
        window = [0] * 26
        base = ord('a')
        for ch in p:
            need[ord(ch) - base] += 1
        ans = []
        for right, ch in enumerate(s):
            window[ord(ch) - base] += 1
            if right >= m:
                window[ord(s[right - m]) - base] -= 1
            if right >= m - 1 and window == need:
                ans.append(right - m + 1)
        return ans

关键代码解释与正确性

right >= m 时，刚加入后长度暂为 m+1，离开位置是 right-m。right >= m-1 保证首个完整窗口已经形成。比较数组而不是集合，才能区分 "aab" 和 "abb"。

初始化 p 的频次正确；每次只对进入和离开的字符做相反更新，归纳可知 window 恰好等于当前窗口频次。固定长度下频次相等与异位词等价，每个起点恰好检查一次，故不漏解也不重复记录。

示例推演：s="cbaebabacd", p="abc"

时间复杂度：O(m+26n)，原题字符集固定为 26，因此记作 O(n+m)。空间复杂度：O(26)=O(1) 辅助空间；输出 O(n-m+1)，最坏 O(n)。若字符集可变，数组比较不再是与 Σ 无关的常数。

解法二：差分数组 + 非零位置计数

定义 diff[c] = window[c] - need[c]，用 mismatch 记录 diff 中非零位置的个数。窗口与 p 相同当且仅当 mismatch=0。每次只改一个字符，先撤销旧的非零贡献，再更新数值，再计入新的非零贡献，避免每轮比较 26 个位置。

from typing import List

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        n, m = len(s), len(p)
        if m == 0 or m > n:
            return []
        base = ord('a')
        diff = [0] * 26
        for ch in p:
            diff[ord(ch) - base] -= 1
        mismatch = sum(value != 0 for value in diff)

        def change(index: int, delta: int) -> None:
            nonlocal mismatch
            mismatch -= int(diff[index] != 0)
            diff[index] += delta
            mismatch += int(diff[index] != 0)

        ans = []
        for right, ch in enumerate(s):
            change(ord(ch) - base, 1)
            if right >= m:
                change(ord(s[right - m]) - base, -1)
            if right >= m - 1 and mismatch == 0:
                ans.append(right - m + 1)
        return ans

关键代码与推演：以 p="ab"、s="abab" 为例，初始 diff[a]=diff[b]=-1，mismatch=2；加入 a 后 a 从 -1→0，mismatch=1；加入 b 后 b 从 -1→0，mismatch=0，记录 0。下个 a 进入时 a 从 0→1，暂为 1；旧 a 离开又从 1→0，恢复 0，记录 1。最后记录 2。

正确性：change 只替换被修改位置对非零总数的贡献，其余位置不变，故 mismatch 始终准确。长度门槛与主解一致，mismatch=0 精确代表所有字符频次相等。

时间复杂度：O(n+m+Σ)，本题 Σ=26；每轮状态更新 O(1)。空间复杂度：O(Σ)=O(1) 辅助空间，输出最坏 O(n)。

易错点与边界检查

• 异位词比较频次，不比较排序前的原字符串，也不能仅比较字符集合。
• 首个完整窗口 right=m-1，移出从 right=m 开始，两个条件相差 1。
• 命中后继续向右移动一位，不能跳过 m 位，否则漏掉重叠答案。
• m>n 返回 []；m=n 时检查一次；s="aa",p="a" 返回 [0,1]；s="ab",p="aa" 返回 []。
• 代码为 p 为空增加防御分支返回 []；原题不出现空 p，本文不把空模式定义为任意位置都匹配。

03LeetCode 76最小覆盖子串

核心知识点：可变窗口、频次覆盖、满足种类数、缺失字符总数

题意与约束

给定 s、t，返回 s 中包含 t 全部字符及其重复次数的最短连续子串；无解返回空串。原题答案唯一，s、t 由大小写英文字母组成，长度均在 1 到 10⁵。大小写应区分。

示例：s="ADOBECODEBANC", t="ABC" → "BANC"；s="a", t="a" → "a"；s="a", t="aa" → ""。本文令 n=|s|、m=|t|。

解法一：需求频次 + 已满足种类数（主解）

need 保存 t 的频次；window 只统计 need 中出现的字符。required = len(need) 是需求字符的种类数，formed 是当前频次已达到需求的种类数。覆盖成立的条件是 formed == required。

1. 右端扩张：对需求字符增加频次，仅在“刚好达到需求”的时刻 formed+=1。
2. 覆盖成立：先用当前合法窗口更新最短答案，再准备删除左端。
3. 若左端字符的频次正好等于需求，删除它会失去一类覆盖，formed-=1；最后减少频次并移动 left。
4. 继续扩张以补足需求。只保存最佳起点和长度，结束时切片一次。

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not t or len(t) > len(s):
            return ""
        need = Counter(t)
        window = {}
        required = len(need)
        formed = 0
        left = 0
        best_start = 0
        best_len = len(s) + 1
        for right, ch in enumerate(s):
            if ch in need:
                window[ch] = window.get(ch, 0) + 1
                if window[ch] == need[ch]:
                    formed += 1
            while formed == required:
                size = right - left + 1
                if size < best_len:
                    best_start, best_len = left, size
                outgoing = s[left]
                if outgoing in need:
                    if window[outgoing] == need[outgoing]:
                        formed -= 1
                    window[outgoing] -= 1
                left += 1
        if best_len == len(s) + 1:
            return ""
        return s[best_start:best_start + best_len]

关键代码解释与正确性

扩张时用 ==，不能用 >=：need[A]=2 时，window[A] 从 1→2 才使 formed 增加，从 2→3 不能再加一次。收缩时在删除前检查相等：从 3→2 仍满足，从 2→1 才会失效。

固定 right 时，while 枚举全部仍覆盖的起点，并在第一次失效前留下最短候选。此前已删除的起点都在合法时记录过；后续 right 更大时，它们只会形成更长窗口，不可能改善答案。遍历所有 right，因此最短覆盖子串必在候选中。

示例推演：s="ADOBECODEBANC", t="ABC"

时间复杂度：O(n+m)，两指针各至多移动 n 次，最后一次切片 O(L)≤O(n)。空间复杂度：O(|Σt|) 辅助空间，只记录 t 的不同字符；返回新字符串另需 O(L)，L 是答案长度。原题英文字母集固定，但保留字符种类参数更清楚。

解法二：差额计数 + 缺失字符总数

remaining[ch] 表示“需求次数减去窗口次数”，可以为负；负值代表有富余。missing 表示仍缺少的字符总个数，初始为 |t|，不是 len(set(t))。只维护需求字符的 remaining。

新字符加入前若 remaining[ch]>0，它填补一个缺口，missing-=1；然后 remaining[ch]-=1。移出字符时先 remaining[ch]+=1，若结果>0，说明刚刚失去一个必需字符，missing+=1。missing=0 时窗口覆盖全部需求。

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not t or len(t) > len(s):
            return ""
        remaining = Counter(t)
        missing = len(t)
        left = 0
        best_start = 0
        best_len = len(s) + 1
        for right, ch in enumerate(s):
            if ch in remaining:
                if remaining[ch] > 0:
                    missing -= 1
                remaining[ch] -= 1
            while missing == 0:
                size = right - left + 1
                if size < best_len:
                    best_start, best_len = left, size
                outgoing = s[left]
                if outgoing in remaining:
                    remaining[outgoing] += 1
                    if remaining[outgoing] > 0:
                        missing += 1
                left += 1
        if best_len == len(s) + 1:
            return ""
        return s[best_start:best_start + best_len]

独立推演：s="AAAB", t="AAB"，初始 remaining={A:2,B:1},missing=3。三个 A 进入后，remaining[A] 依次为 1、0、-1，missing 依次为 2、1、1；B 进入后 missing=0。先记录 "AAAB"，移出一个富余 A 后 remaining[A]=0，仍覆盖；记录 "AAB"，再移出 A 后 remaining[A]=1、missing=1，停止。返回 "AAB"。

正确性：始终有 missing=Σ max(remaining[c],0)，因此 missing=0 等价于所有需求满足。进入和移出只改变当前字符的缺口，计数始终准确；合法时收缩的最优性证明仍可直接应用于这一状态定义。

时间复杂度：O(n+m)。空间复杂度：O(|Σt|) 辅助空间，输出另需 O(L)。不可删除 remaining 中值为 0 的键，否则会丢失对该需求字符的后续追踪。

易错点与边界检查

• t="AAB" 需要两个 A，不能只检查集合；formed 与 missing 的初值和含义不能混用。
• 必须在窗口仍合法时更新答案，再删除左端。最短问题不能照搬“非法时收缩”的条件。
• 若每次发现候选就切片，可能累计 O(n²) 拷贝；保存起点、长度，最后切片一次。
• 无解返回空串；t 比 s 长立即返回空串；t 为空的防御分支也返回空串。
• s="aA",t="A" 返回 "A"；s="AAAB",t="AAB" 返回 "AAB"；s="abc",t="z" 返回 ""。

04LeetCode 239滑动窗口最大值

核心知识点：双端队列、下标过期、单调性、摊还分析、堆、分块

题意与约束

给定整数数组 nums 和窗口长度 k，从左向右每次移动一位，返回每个长度为 k 的连续窗口中的最大值。原题 1≤k≤n≤10⁵，元素范围为 [-10⁴,10⁴]。

示例：nums=[1,3,-1,-3,5,3,6,7], k=3 → [3,3,5,5,6,7]；nums=[1],k=1 → [1]。

从暴力法到候选淘汰

对每个窗口重新调用 max，需要 O((n-k+1)k) 时间，最坏 O(n²)；只存一个最大值又无法处理它离开窗口后的继任者。需要保留未来仍可能成为最大值的候选。

若 i<j 且 nums[i]≤nums[j]，则 j 比 i 晚过期，值又不小。在今后仍包含 i 的窗口里也一定包含 j，所以 i 不可能优于 j，可以永久删除。这就是单调队列的支配关系。

解法一：递减双端队列（线性主解）

不变量：队列存下标，下标从队首到队尾递增，对应值严格递减；队列下标都在当前窗口范围内。队首即最大值的下标。

1. 先移出过期下标：当前 left=right-k+1，队首≤right-k 就过期。
2. 从队尾删除值≤当前值的候选，保留更新且不小的当前元素。
3. 把 right 入队；right≥k-1 时记录队首值。

from collections import deque
from typing import List

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums or k <= 0 or k > len(nums):
            return []
        queue = deque()
        ans = []
        for right, value in enumerate(nums):
            while queue and queue[0] <= right - k:
                queue.popleft()
            while queue and nums[queue[-1]] <= value:
                queue.pop()
            queue.append(right)
            if right >= k - 1:
                ans.append(nums[queue[0]])
        return ans

关键代码解释与正确性

queue[0] <= right-k 刚好排除 left 左边的下标。队尾用 <= 淘汰等值旧下标，使值严格递减；用 < 保留等值下标也正确，但需与“不增”的不变量一致。

过期元素不能影响当前或未来窗口；被队尾淘汰的元素由更晚且不小的元素支配。所有可能影响最大值的候选因此都被保留或有支配者保留。队列按值递减，队首就是当前窗口最大值。

示例推演：队列展示为 下标:值

时间复杂度：O(n)。单轮可能连续弹出多个元素，但每个下标入队一次、最多出队一次，总操作 O(n)。空间复杂度：O(k) 辅助空间，严格递减数组中队列可保留 k 个下标；输出另需 O(n-k+1)。

解法二：最大堆 + 惰性删除

Python heapq 是最小堆，把 (-value,index) 入堆模拟最大堆。只要堆顶下标过期就弹出，直到堆顶属于当前窗口，再读取堆顶值。埋在堆内部的旧元素暂不处理；当它将来成为堆顶时再删除。

import heapq
from typing import List

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if not nums or k <= 0 or k > len(nums):
            return []
        heap = []
        ans = []
        for right, value in enumerate(nums):
            heapq.heappush(heap, (-value, right))
            while heap and heap[0][1] <= right - k:
                heapq.heappop(heap)
            if right >= k - 1:
                ans.append(-heap[0][0])
        return ans

关键代码与独立推演：nums=[9,1,2],k=2。right=1 时堆顶 (-9,0) 未过期，输出 9；right=2 时下标 0≤2-2，弹出旧 9，再读到有效堆顶 (-2,2)，输出 2。结果 [9,2]。用 while 而不是 if，确保连续多个过期堆顶都被移除。

正确性：所有进入过的元素都入堆；堆内有效元素尚未被删除。移除过期堆顶后，堆顶是所有剩余元素中值最大的，且属于当前窗口，所以也是当前窗口最大值。

时间复杂度：O(n log n)，每个元素入堆一次、至多弹出一次。空间复杂度：O(n) 辅助空间，输出 O(n-k+1)。这种只清理堆顶的版本不能写成 O(k) 空间或保证 O(n log k)：严格递增数组里旧小值长期埋在堆中，堆规模可能达到 n。

解法三：分块前缀 / 后缀最大值

按 k 个元素一块分组，最后一块允许不足 k。prefix[i] 记录所在块的块首到 i 的最大值；suffix[i] 记录 i 到块尾的最大值。长度为 k 的窗口 [left,right] 要么正好一整块，要么横跨相邻两块，故答案是两端片段最大值的较大者。

from typing import List

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        if n == 0 or k <= 0 or k > n:
            return []
        prefix = [0] * n
        suffix = [0] * n
        for i in range(n):
            if i % k == 0:
                prefix[i] = nums[i]
            else:
                prefix[i] = max(prefix[i - 1], nums[i])
        for i in range(n - 1, -1, -1):
            if i == n - 1 or (i + 1) % k == 0:
                suffix[i] = nums[i]
            else:
                suffix[i] = max(suffix[i + 1], nums[i])
        return [max(suffix[left], prefix[left + k - 1])
                for left in range(n - k + 1)]

关键代码与独立推演：nums=[1,3,-1,-3,5,3,6,7],k=3，块为 [1,3,-1] | [-3,5,3] | [6,7]。prefix=[1,3,3,-3,5,5,6,7]，suffix=[3,3,-1,5,5,3,7,7]。窗口 [1,3] 的答案=max(suffix[1],prefix[3])=max(3,-3)=3；窗口 [5,7] 得 max(3,7)=7。完整结果为 [3,3,5,5,6,7]。

正确性：块内前缀、后缀数组由相邻最大值递推得到。窗口横跨块边界时，两片段恰好覆盖窗口；窗口与整块对齐时，两端片段各等于整块，公式仍成立。最后短块用 i==n-1 作为后缀初始化边界，不能漏掉。

时间复杂度：O(n)，两次预处理加一次输出。空间复杂度：O(n) 辅助空间，输出另需 O(n-k+1)。适合离线整数组处理，须先获得整个数组；单调队列更适合边读边输出。

易错点与边界检查

• 队列存下标，才能判断过期与区分相同值。不能简单用 set 存候选值。
• 列表 pop(0) 是 O(k)，需要 collections.deque 的 popleft()。
• right=k-1 才产生首个答案，总输出数 n-k+1。
• 全负数不能用 0 作为默认最大值；分块数组虽然初始为 0，但每个元素都在读取前被正确赋值。
• k=1 输出原数组各值；k=n 输出一个全局最大值；[2,2,2],k=2 返回 [2,2]；[-4,-2,-5],k=2 返回 [-2,-2]。
• 三种提交代码都对空数组、k≤0、k>n 返回 []；这些是原题有效约束以外的防御处理。