3.4　滑动窗口

学习目标：学完本节，你能

• 识别哪些问题属于"滑动窗口"型；
• 写出定长窗口与变长窗口两种模板；
• 解释为什么嵌套了 while 循环，复杂度仍然是 $O(n)$；
• 说清滑动窗口相对暴力的真正优势 —— 不只是快，而是稳定。

先修：3.3（双指针）、1.3（最好/最坏/平均）。 固定术语：滑动窗口、窗口、左右边界。 环境与版本：.NET 8 / C# 12。 预计阅读：30 分钟。

一、直觉：取景框

想象你手里有一个取景框，在一个长条形的画卷上滑动：

• 框的右边不断向右扩大，把新内容纳入视野；
• 框的左边根据需要向右收缩，把不合要求的内容挤出去；
• 你始终只关心框里的内容。

这就是滑动窗口（Sliding Window）：维护一个连续区间 $[left, right]$，随着遍历不断调整它的两个边界。

它解决的问题类型非常固定：

在一个数组或字符串中，找一个满足某种条件的连续子区间。

比如：

• 长度为 $k$ 的子数组最大和
• 最长的无重复字符子串
• 和大于等于 $target$ 的最短子数组
• 包含某字符串所有字母的最小子串

二、关键洞察：两个边界都只前进，不后退

这是滑动窗口能做到 $O(n)$ 的全部原因。

回顾 3.3 节的暴力解法：对每个起点 $i$，都从 $i$ 开始重新往后扫描 —— 同一个元素被反复检查了无数次。

滑动窗口不一样：

• $right$ 从 0 走到 $n-1$，只往右。
• $left$ 也从 0 走到最多 $n-1$，只往右。

两个指针加起来最多走 $2n$ 步。

即使代码里写了嵌套的 while，left 在整个过程中总的移动次数也不超过 $n$ —— 因为它从不后退，退回去的那些工作就永远省下来了。

这就是为什么滑动窗口是 $O(n)$ 而不是 $O(n^2)$：不是因为"循环少了一层"，而是因为每个元素最多被 left 和 right 各扫过一次。

三、两种窗口

四、定长窗口：进一个、出一个

新建控制台项目，粘贴以下完整代码：

using System.Diagnostics;
using System.Text;

// ==================== 定长窗口：长度为 k 的子数组最大和 ====================

// 暴力：每个窗口都从头重新求和，O(n*k)
static long MaxSumBrute(int[] a, int k, ref long ops)
{
    long best = long.MinValue;
    for (int i = 0; i + k <= a.Length; i++)
    {
        long sum = 0;
        for (int j = i; j < i + k; j++)
        {
            sum += a[j];
            ops++;
        }
        if (sum > best) best = sum;
    }
    return best;
}

// 滑动窗口：进一个、出一个，O(n)
static long MaxSumWindow(int[] a, int k, ref long ops)
{
    long sum = 0;
    for (int i = 0; i < k; i++) { sum += a[i]; ops++; }        // 第一个窗口
    long best = sum;

    for (int i = k; i < a.Length; i++)
    {
        sum += a[i] - a[i - k];                                // 进 a[i]，出 a[i-k]
        ops++;
        if (sum > best) best = sum;
    }
    return best;
}

// ==================== 变长窗口：最长无重复字符子串 ====================

// 暴力：以每个位置为起点往后扩展，O(n^2)
static int LongestSubstringBrute(string s, ref long ops)
{
    int best = 0;
    for (int i = 0; i < s.Length; i++)
    {
        var seen = new HashSet<char>();
        for (int j = i; j < s.Length; j++)
        {
            ops++;
            if (!seen.Add(s[j])) break;      // 出现重复，这个起点的探索结束
            if (j - i + 1 > best) best = j - i + 1;
        }
    }
    return best;
}

// 滑动窗口：左右边界都只前进不后退，O(n)
static int LongestSubstringWindow(string s, ref long ops)
{
    var lastSeen = new Dictionary<char, int>();   // 字符 -> 最近一次出现的下标
    int left = 0, best = 0;

    for (int right = 0; right < s.Length; right++)
    {
        ops++;
        char c = s[right];

        // 如果这个字符在窗口内出现过，左边界直接跳到它后面
        if (lastSeen.TryGetValue(c, out int pos) && pos >= left)
            left = pos + 1;

        lastSeen[c] = right;
        if (right - left + 1 > best) best = right - left + 1;
    }
    return best;
}

// ---- 两种输入分布 ----

// A：完全随机。字符集 95 个可打印 ASCII
static string MakeRandom(int n, Random r)
{
    var sb = new StringBuilder(n);
    for (int i = 0; i < n; i++) sb.Append((char)(' ' + r.Next(95)));
    return sb.ToString();
}

// B：长周期。每 period 个字符才重复一次，所以最长无重复窗口 = period
static string MakePeriodic(int n, int period)
{
    var sb = new StringBuilder(n);
    for (int i = 0; i < n; i++) sb.Append((char)(' ' + i % period));
    return sb.ToString();
}

// ==================== 主流程 ====================

var rng = new Random(42);
const int N = 100_000;
const int N2 = 50_000;
const int K = 1_000;
const int Period = 1_000;

int[] data = new int[N];
for (int i = 0; i < N; i++) data[i] = rng.Next(1, 1000);

Console.WriteLine("=== 实验一：长度为 k 的子数组最大和 ===");
Console.WriteLine($"数据规模 {N:N0}，窗口大小 {K:N0}");

long bo = 0, wo = 0;
var sw = Stopwatch.StartNew();
long b1 = MaxSumBrute(data, K, ref bo);
sw.Stop();
double bMs = sw.Elapsed.TotalMilliseconds;

sw.Restart();
long w1 = MaxSumWindow(data, K, ref wo);
sw.Stop();
double wMs = sw.Elapsed.TotalMilliseconds;

Console.WriteLine($"  暴力（每个窗口重新求和）: 加法 {bo,12:N0} 次 | {bMs,8:F2} ms | 结果 = {b1:N0}");
Console.WriteLine($"  滑动窗口（进一个出一个）: 加法 {wo,12:N0} 次 | {wMs,8:F2} ms | 结果 = {w1:N0}");
Console.WriteLine($"  结果一致: {b1 == w1}   滑动窗口少算 {bo / (double)wo:N0} 倍");
Console.WriteLine();

Console.WriteLine("=== 实验二：最长无重复字符子串 —— 先验证正确性 ===");
var samples = new[] { "abcabcbb", "bbbbb", "pwwkew", "", "abcdefg", "abba" };
foreach (var s in samples)
{
    long o1 = 0, o2 = 0;
    int rb = LongestSubstringBrute(s, ref o1);
    int rw = LongestSubstringWindow(s, ref o2);
    Console.WriteLine($"    \"{s,-10}\" 暴力={rb}  滑窗={rw}  一致={rb == rw}");
}
Console.WriteLine();

Console.WriteLine("=== 实验三：同样的两个算法，换一种输入，差距差了 100 倍 ===");
Console.WriteLine();

// --- 输入 A：完全随机 ---
string randText = MakeRandom(N2, rng);
long aOps = 0, aOps2 = 0;
sw.Restart();
int aB = LongestSubstringBrute(randText, ref aOps);
sw.Stop();
double aMs = sw.Elapsed.TotalMilliseconds;
sw.Restart();
int aW = LongestSubstringWindow(randText, ref aOps2);
sw.Stop();
double aMs2 = sw.Elapsed.TotalMilliseconds;

Console.WriteLine($"  输入 A：完全随机（{N2:N0} 个字符，字符集 95）");
Console.WriteLine($"    最长无重复子串长度 = {aB}");
Console.WriteLine($"    暴力    : 探测 {aOps,12:N0} 次 | {aMs,8:F2} ms");
Console.WriteLine($"    滑动窗口: 探测 {aOps2,12:N0} 次 | {aMs2,8:F2} ms");
Console.WriteLine($"    滑动窗口少探测 {(double)aOps / aOps2:N0} 倍");
Console.WriteLine();

// --- 输入 B：长周期 ---
string periodicText = MakePeriodic(N2, Period);
long bOps = 0, bOps2 = 0;
sw.Restart();
int bB = LongestSubstringBrute(periodicText, ref bOps);
sw.Stop();
double bMs2 = sw.Elapsed.TotalMilliseconds;
sw.Restart();
int bW = LongestSubstringWindow(periodicText, ref bOps2);
sw.Stop();
double bMs3 = sw.Elapsed.TotalMilliseconds;

Console.WriteLine($"  输入 B：长周期（{N2:N0} 个字符，每 {Period:N0} 个才重复一次）");
Console.WriteLine($"    最长无重复子串长度 = {bB}");
Console.WriteLine($"    暴力    : 探测 {bOps,12:N0} 次 | {bMs2,8:F2} ms");
Console.WriteLine($"    滑动窗口: 探测 {bOps2,12:N0} 次 | {bMs3,8:F2} ms");
Console.WriteLine($"    滑动窗口少探测 {(double)bOps / bOps2:N0} 倍");
Console.WriteLine();

Console.WriteLine("  两种输入下，滑动窗口的探测次数完全一样（都是 50,000 次），");
Console.WriteLine("  但暴力的探测次数从 64 万涨到了 5000 万 —— 涨了约 77 倍。");
Console.WriteLine();
Console.WriteLine("  滑动窗口的价值不只是「更快」，更是「不管输入长什么样都同样快」。");

实测输出（.NET 8 Release）：

=== 实验一：长度为 k 的子数组最大和 ===
数据规模 100,000，窗口大小 1,000
  暴力（每个窗口重新求和）: 加法   99,001,000 次 |    25.36 ms | 结果 = 530,908
  滑动窗口（进一个出一个）: 加法      100,000 次 |     0.54 ms | 结果 = 530,908
  结果一致: True   滑动窗口少算 990 倍

=== 实验二：最长无重复字符子串 —— 先验证正确性 ===
    "abcabcbb  " 暴力=3  滑窗=3  一致=True
    "bbbbb     " 暴力=1  滑窗=1  一致=True
    "pwwkew    " 暴力=3  滑窗=3  一致=True
    "          " 暴力=0  滑窗=0  一致=True
    "abcdefg   " 暴力=7  滑窗=7  一致=True
    "abba      " 暴力=2  滑窗=2  一致=True

=== 实验三：同样的两个算法，换一种输入，差距差了 100 倍 ===

  输入 A：完全随机（50,000 个字符，字符集 95）
    最长无重复子串长度 = 43
    暴力    : 探测      646,160 次 |    12.13 ms
    滑动窗口: 探测       50,000 次 |     0.81 ms
    滑动窗口少探测 13 倍

  输入 B：长周期（50,000 个字符，每 1,000 个才重复一次）
    最长无重复子串长度 = 1000
    暴力    : 探测   49,549,500 次 |   360.56 ms
    滑动窗口: 探测       50,000 次 |     0.35 ms
    滑动窗口少探测 991 倍

  两种输入下，滑动窗口的探测次数完全一样（都是 50,000 次），
  但暴力的探测次数从 64 万涨到了 5000 万 —— 涨了约 77 倍。

五、读实验一：进一个，出一个

定长窗口的代码只有一行是关键：

sum += a[i] - a[i - k];      // 进 a[i]，出 a[i-k]

对比两种做法的加法次数：

990 倍的差距，全部来自一个观察：相邻两个窗口有 $k-1$ 个元素是重叠的，重算是纯浪费。

窗口从 [0, k) 滑到 [1, k+1) 时，只有两个变化：

• 左边少了一个 a[0]
• 右边多了一个 a[k]

所以新窗口的和 = 旧窗口的和 $-\ a[0] +\ a[k]$。$O(1)$ 完成，不需要重新累加。

这个"增量更新"是滑动窗口的核心手法：不要重新计算整个窗口的状态，而是根据"进什么、出什么"增量地更新它。

六、读实验三：滑动窗口真正的价值

实验三的数据值得反复看：

两个算法都没变，输入变了，差距从 13 倍变成了 991 倍。

为什么输入 A 的暴力没那么慢？

因为随机字符串里，窗口天然就很短。字符集只有 95 个，随机情况下大约十几个字符就会撞上重复（实测最长 43，平均只有十几个）。所以暴力的内层循环跑不了几步就 break 了。

为什么输入 B 的暴力那么慢？

因为构造的字符串是"每 1000 个字符才重复一次"。最长无重复子串长达 1000，暴力的内层循环每次都要真正跑满 1000 步，总共 $50{,}000 \times 1000 \approx 5 \times 10^7$ 次。

而滑动窗口在两种输入下都是 50,000 次，一步不多、一步不少。

这才是滑动窗口最重要的价值：

暴力的代价取决于"运气"，滑动窗口的代价是"保证"的。

在生产环境里，你往往无法控制输入数据的分布 —— 用户可能上传一个完全由重复字符组成的文件，也可能是精心构造的对抗性输入。一个"最坏情况有保障"的算法，比一个"平均很快"的算法更让人安心。

这也正是 1.3 节讲的：工程决策看最坏情况。

七、通用模板

变长窗口的模板（最常用，建议记熟）：

int left = 0;
int answer = 0;                      // 或 long.MaxValue（求最小值时）

for (int right = 0; right < n; right++)
{
    // ① 把 a[right] 加入窗口，更新窗口状态
    AddToWindow(a[right]);

    // ② 当窗口不满足条件时，收缩左边界，直到重新合法
    while (窗口不合法() && left <= right)
    {
        RemoveFromWindow(a[left]);
        left++;
    }

    // ③ 此时窗口是合法的，用它更新答案
    answer = Math.Max(answer, right - left + 1);
}

return answer;

三个步骤的分工：

难点在 ②：定义清楚"什么样的窗口是合法的"。

以"最长无重复子串"为例：

• 合法 = 窗口内没有重复字符。
• 当新加入的字符 c 已经在窗口内出现过（位置 pos ≥ left）时，窗口就不合法了。
• 收缩方式是：直接把 left 跳到 pos + 1，而不是一格一格挪。

这里的"直接跳"是个优化：因为 pos 之前的位置都还在窗口里的话，c 依然是重复的。一次性跳过去，比一步步挪更快，而且让代码更简洁。

注意：即使写成 while 一格一格挪，复杂度仍然是 $O(n)$ —— 因为 left 总移动次数不超过 $n$。"直接跳"优化的是常数，不是量级。

为什么嵌套 while 还是 $O(n)$？

这是最多人困惑的地方。关键在于均摊分析：

• right 一共走 $n$ 步（外层 for）。
• left 一共也走最多 $n$ 步 —— 因为 left 只增不减。
• 所以两个指针的总移动次数 $\le 2n = O(n)$。

内层 while 不是"对每个 right 都跑一遍"，而是"在整个算法生命周期里总共跑 n 次"。 这是均摊分析的典型应用 —— 和 3.2 节 List<T> 的"扩容总搬运量小于 $2n$"是同一个思路。

八、滑动窗口 vs 前缀和

3.4 和 1.4 节的前缀和都能解决"区间"类问题，怎么选？

判断口诀：

• 问题问的是"某个区间的和是多少"，而且查询很多次 → 前缀和
• 问题问的是"最长的/最短的/最大的满足某条件的连续区间在哪" → 滑动窗口

两者不是竞争关系。 有些问题两个都能解，但更常见的是只有一个是自然的 —— 比如"最长无重复子串"用前缀和就无从下手（没有可减的"和"），而"求区间和"用滑动窗口也很难做（因为查询区间是任意的、不连续的）。

九、练习

练习 3.4.1（识别） 下面五个问题，哪些适合用滑动窗口？ (a) 求数组中第 $k$ 大的元素 (b) 求最长的不含重复字符的子串 (c) 求和大于等于 $target$ 的最短连续子数组（数组元素全为正数） (d) 求数组中所有元素的和 (e) 判断字符串 $s$ 中是否包含字符串 $t$ 的某个排列（即 $t$ 的字母重排后是否是 $s$ 的子串）

练习 3.4.2（定长窗口） 一个数组里有正有负。用滑动窗口求"长度为 $k$ 的子数组最大和"时，"进一个出一个"的方法还成立吗？为什么？ （提示：想想"进一个出一个"依赖的是什么性质。）

练习 3.4.3（写代码） 用滑动窗口实现：给定一个全是正数的数组和一个目标值 target，找出和大于等于 target 的最短连续子数组，返回它的长度。如果不存在，返回 0。

练习 3.4.4（复杂度分析） 下面这段代码看起来有两层循环，请说明它为什么仍是 $O(n)$：

int left = 0, sum = 0;
for (int right = 0; right < n; right++)
{
    sum += a[right];
    while (sum > target && left <= right)
    {
        sum -= a[left];
        left++;
    }
}

练习 3.4.5（挑战·变体） 给定一个字符串，找出最多包含 $k$ 个不同字符的最长子串。 (a) "窗口合法"的定义是什么？ (b) 什么时候需要收缩左边界？ (c) 用哈希表记录什么？写出完整代码。

十、练习答案

3.4.1

• (a) 不适合。 这是"选择问题"，应该用堆（第 11 章）或快速选择。它和"连续区间"毫无关系。
• (b) 适合。 典型的变长窗口问题。
• (c) 适合。 变长窗口。"数组元素全为正数"这个条件是关键（见练习 3.4.2 的答案）。
• (d) 不适合。 全部元素的和，一次遍历就够，不需要"窗口"的概念。
• (e) 适合。 定长窗口 —— 窗口长度固定为 $t$ 的长度，滑动检查每个窗口的字符构成是否和 $t$ 一致。

判断口诀：问题是不是在问"某个连续子区间"？ 是的话就值得考虑滑动窗口。

3.4.2

仍然成立。

"进一个、出一个"依赖的性质是：新窗口的和 = 旧窗口的和 − 左边移出的元素 + 右边移入的元素。

这个等式只依赖"窗口是连续的"这个事实，和元素的正负完全无关。

sum += a[i] - a[i - k];     // 无论 a[i] 是正是负都成立

所以"有正有负"不影响定长窗口的正确性。

但变长窗口就没这么幸运了。 练习 3.4.3 的"和大于等于 target 的最短子数组"必须要求全为正数，原因是：

滑动窗口要成立，需要单调性：当窗口的和已经大于 target 时，再往右扩只会更大，所以可以放心收缩左边。

如果有负数，这个单调性就没了 —— 扩大窗口反而可能让和变小，那么"收缩左边"就未必是正确的一步。这时应该改用前缀和 + 哈希表（15.2 节会讲这个技巧）。

3.4.3

static int MinSubArrayLen(int target, int[] a)
{
    int left = 0;
    long sum = 0;
    int best = int.MaxValue;

    for (int right = 0; right < a.Length; right++)
    {
        sum += a[right];                        // ① 扩张

        while (sum >= target)                   // ② 满足条件了，尝试收缩看能不能更短
        {
            best = Math.Min(best, right - left + 1);
            sum -= a[left];
            left++;
        }
    }

    return best == int.MaxValue ? 0 : best;
}

验证（target = 7，a = [2,3,1,2,4,3]）：

答案是 3（子数组 [4, 3]）✓ 与题目给出的经典答案一致。

注意 while 的条件是 sum >= target（不是 sum > target），因为题目要求的是"大于等于"。

这个模板和"最长"类问题的模板有一个区别：这里在 ② 收缩的过程中就更新答案，而不是等收缩完。因为"最短"类问题要抓住每一个满足条件的瞬间。

3.4.4

因为它满足均摊分析的条件：left 只增不减。

拆开来数：

• 外层 for 让 right 从 0 走到 $n-1$，共 $n$ 步。
• 内层 while 每执行一次，left 就 +1。
• 而 left 从 0 开始，永远不会超过 $right$（有条件 left <= right），所以 left 在整个算法中最多增加 $n$ 次。

因此，内层 while 的总执行次数不超过 $n$，而不是"每次外层循环都执行 $n$ 次"。

总操作次数 $\le n + n = 2n = O(n)$。

一个常见的误解："嵌套循环就是 $O(n^2)$"。这是 1.2 节就强调过的错误 —— 要看内层循环的总执行次数，而不是看它嵌套了几层。

对比一下：如果 left 每次都被重置为 0（比如在每个 right 上都重新收缩一遍），内层就会真的跑 $O(n)$ 次，总共变成 $O(n^2)$。"只增不减"是这里的命门。

3.4.5

(a) 窗口合法的定义：窗口内不同字符的个数 $\le k$。

(b) 收缩时机：当窗口内不同字符个数 $> k$ 时，说明左边界必须右移，直到不同字符个数重新 $\le k$。

(c) 哈希表记录什么：记录窗口内每个字符出现的次数。

• 加入一个字符时：计数 +1，如果这个字符是新出现的（计数从 0 变 1），则不同字符数 +1。
• 移除一个字符时：计数 −1，如果计数变成 0，则不同字符数 −1。

完整代码：

static int LongestSubstringKDistinct(string s, int k)
{
    if (k == 0) return 0;

    var count = new Dictionary<char, int>();   // 窗口内每个字符出现几次
    int left = 0;
    int best = 0;

    for (int right = 0; right < s.Length; right++)
    {
        // ① 扩张：加入 s[right]
        char c = s[right];
        count.TryGetValue(c, out int cur);
        count[c] = cur + 1;

        // ② 收缩：不同字符超过 k 个时，从左边踢字符出去
        while (count.Count > k)
        {
            char lc = s[left];
            count[lc]--;
            if (count[lc] == 0)
                count.Remove(lc);              // 计数归零就删掉，count.Count 才是"不同字符数"
            left++;
        }

        // ③ 记录：此时窗口内不同字符数一定 <= k
        best = Math.Max(best, right - left + 1);
    }

    return best;
}

几个关键点：

1. 用 count.Count 表示"不同字符数"。 所以计数归零时必须 Remove，否则 Count 会把"计数为 0 的键"也算进去，判断就错了。这是本题最容易出的 bug。
2. while 会连续踢出多个字符，直到不同字符数降到 $k$。这正是变长窗口模板里 ② 的标准形态。
3. 复杂度：$right$ 走 $n$ 步，$left$ 总共最多走 $n$ 步，所以是 $O(n)$。哈希表的操作是 $O(1)$ 均摊，整体 $O(n)$。

验证（s = "eceba"，k = 2）：

• 最长子串是 "ece"（2 个不同字符），长度 3 ✓

十一、常见错误

十二、本节总结

1. 滑动窗口维护一个连续区间 $[left, right]$，专门解决"找满足条件的连续子区间"这类问题。
2. 核心性质：两个边界都只前进、不后退，所以总共最多走 $2n$ 步，是 $O(n)$。
3. 嵌套 while 不改变复杂度 —— 因为 left 的总移动次数不超过 $n$（均摊分析）。
4. 两种形态：定长窗口用"进一个出一个"（$O(1)$ 增量更新）；变长窗口用"右扩左缩"。
5. 实测差距：定长窗口比暴力少算 990 倍；变长窗口在长周期输入下少探测 991 倍。
6. 滑动窗口真正的价值是"稳定"：不管输入什么，它都走 $2n$ 步。而暴力的代价完全取决于输入分布（实测在两种输入下差了 77 倍）。
7. 前提是单调性：变长窗口要求"窗口越扩，越难满足条件"（或越容易）。有负数时这个前提可能失效。

本章小结：第 3 章把最基础的数据结构 —— 数组 —— 从里到外讲了一遍。

• 3.1 让你知道"连续内存"这四个字意味着什么：$O(1)$ 随机访问、$O(n)$ 中间插入、以及大 O 看不见的缓存红利。
• 3.2 让你亲手实现了 List<T>，把"摊还 $O(1)$"从一句口号变成了一个可证明的结论。
• 3.3 和 3.4 给了你两把"降维"的钥匙：双指针和滑动窗口。它们能把大量看着像 $O(n^2)$ 的问题降到 $O(n)$，而且是面试和实际工作中出现频率最高的技巧。

下一章衔接：数组最大的痛点是"中间插入要挪动一堆元素"。有没有一种结构，插入和删除本身是 $O(1)$ 的？有 —— 链表。但天下没有免费的午餐：链表用失去随机访问和缓存友好性，换来了 $O(1)$ 的插入删除。第 4 章我们会把这两者的取舍算得清清楚楚，而不是停留在"链表插入快"这种口号上。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "3.4",
  "title": "滑动窗口",
  "covered": [
    "滑动窗口的定义与适用问题类型",
    "「两个边界都只前进」是 O(n) 的根本原因",
    "定长窗口（进一个出一个）与增量更新",
    "变长窗口（右扩左缩）与合法性定义",
    "通用模板三步与均摊分析",
    "两种输入分布下的实测对比（13 倍 vs 991 倍）",
    "滑动窗口 vs 前缀和的选择依据",
    "单调性前提与负数场景的失效"
  ],
  "unresolved": [
    "前缀和 + 哈希表处理负数场景留到 15.2",
    "定长窗口的字符构成比较可结合哈希表（第 6 章）",
    "堆解决 Top-K 留到 11.4"
  ],
  "canonical_terms": {
    "滑动窗口": "维护一个连续区间并滚动，左右边界都只前进",
    "窗口": "当前处理的连续子区间 [left, right]",
    "左右边界": "窗口的两个端点，在滑动窗口算法中都只增不减"
  },
  "symbols_units": {},
  "assumptions": [
    "读者已掌握 3.3 的双指针与 1.3 的最好/最坏/平均",
    "读者会使用 Dictionary<char,int> 的基本操作"
  ],
  "word_count_actual": 2620,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch03/Sec34/",
    "实测数据逐项核对：定长 99001000 vs 100000；变长 A 646160 vs 50000；变长 B 49549500 vs 50000",
    "6 个边界用例（含空串、全同字符、abba）暴力与滑窗结果逐项一致",
    "练习答案含关键步骤，不只给结果",
    "术语写法与 glossary.md 一致"
  ],
  "known_issues": [
    "初版用 26 个字母的随机串做大规模对比，因随机串中无重复窗口期望仅 O(sqrt(字符集)) 导致暴力跑不满、差距只显示 7 倍；已改为「随机 vs 长周期」两种输入分布的对比，并把这个现象本身写成教学点"
  ],
  "next": "4.1 节点与引用：链表的本质"
}