两个下标盯住一段
这一课只练一件事:用 维护一段连续区间。左边那个下标叫 left,右边那个叫 right,中间那一段就是 。先判断 成不成立,再决定移动哪一边。用 a = [1, 2, 3]、和不超过 3 走三步,并核对空窗口与满窗口。n 到 1e5 时,每个指针只往右走,大约是 ,比两层循环更能通过。单调队列、三数之和是拓展。这里不会在浏览器里运行 C++。
任务 1:先选出两个指针是什么、窗口怎么维护
不是随便两个无关变量。它们是 和 ,一起圈出当前的 。点不认识的词可看基础解释。
必会:能说出 left 和 right 分别管哪一端,并能保持窗口条件。这里不会在浏览器里运行 C++,只练习选择和走过程。
left 和 right 表示什么?双指针 · 必会
窗口条件被破坏时该怎么办?窗口条件 · 必会
任务 2:按顺序给 [1, 2, 3] 扩窗口
最小示例:下标从 1 开始,a[1]=1,a[2]=2,a[3]=3,窗口里的数加起来不能超过 3。按顺序点三步,先从空窗口 left = 1, right = 0 开始,再让 right = 1 纳入 1,最后让 right = 2 得到 sum = 3。这里不会在浏览器里运行 C++。
必会:能解释每一步窗口怎么变。边界:空窗口时 right 还在 left 左边;不要跳过纳入 a[1] 这一步。n 到 1e5 时,每个指针只往右走,大约 n 次移动,比两层循环更能通过。
- int a[4] = {0, 1, 2, 3}; // a[1..3]
- int left = 1, right = 0, sum = 0;
- right++; sum += a[right];
- // 若 sum > 3:sum -= a[left]; left++;
窗口扩完了,现在亲手把扩大窗口的那一行敲出来:先移动 ,再把新纳入的数折进 的和。下面是只读脚手架,只留一空给你敲键盘。
- int a[4] = {0, 1, 2, 3}; // a[1..3]
- int left = 1, right = 0, sum = 0;
- while (right < 3) {
- ; // 扩大窗口
- if (sum > 3) { sum -= a[left]; left++; }
- }
right++; sum += a[right]; // right 从 0 走到 1,sum 从 0 变成 1
任务 3:核对空窗口、满窗口,以及下一步怎么走
建议掌握:空窗口是 right < left,里面一个数都没有。现在窗口是 [1, 2],sum = 3,已经满了:再纳入 a[3]=3 会破坏 。不要把 left 和 right 一起乱加。
必会 / 建议掌握 / 拓展:必会是说出两个指针的含义并保持条件。建议掌握是验证空窗口和满窗口,以及只移动会恢复条件的那一边。单调队列、三数之和是拓展,现在不用当硬门槛。
- // 空窗口:left = 1, right = 0
- // 当前满窗口:[1, 2],sum = 3
- // 若再 right++ 纳入 3:sum = 6 > 3
- // 应 left++ 丢掉 1,而不是两边一起跳
先选出空窗口长什么样:
再选出窗口已满、条件将被破坏时该怎么做:
任务 4:随机小测,看看你是否真的懂了
每次从本课题库抽出三道不同的选择题。题目与解析已通过校验,答完后看解析,不要只看分数;拿不准就回到对应任务再看一遍。