洛谷P1638逛画展：滑动窗口与双指针经典解法详解

刷算法竞赛题的人多半经历过这种时刻拿到一道题条件反射地往复杂了想折腾半天结果发现正解不过是一层窗户纸。洛谷 P1638 逛画展就是这道经典的“窗户纸”。它常年躺在洛谷双指针题单里每到CSP/NOIP备考季都会被一大批选手翻出来重刷。题目本身不长但信息量不小一排画、若干画家、求一个最短的连续区间让所有画家的作品都在里面。看懂题目可能只需要五秒但能把代码一次写对我见过不少初学者要花半个小时。因为这道题真正考的是滑动窗口最核心的单调性理解右指针往右走的时候左指针为什么可以放心地跟着往右走而不用回头。这篇文章我会从题意解读、双指针原理、完整C实现一路讲到调试踩坑和同类题迁移争取让你刷完这一题顺便带走一个能套用到很多地方的通用模板。1. 为什么这道题值得刷题目本质与考点拆解1.1 先把题目读懂逛画展到底要我们干什么P1638的题目背景是逛画展翻译成算法语言其实非常简单。给定一个长度为n的数组a数组里的每个元素a[i]表示第i幅画的作者编号编号范围是1到m。要求找出一个最短的连续子数组使得这个子数组里完整包含1到m这m个编号也就是说所有画家的作品至少出现一次。如果存在多个长度相同的最短区间输出左端点最小的那一个。举个具体的例子。假设n5m2数组是1 2 1 1 2这里画家编号只有1和2两种。能同时包含1和2的区间有[1,2]、[2,3]、[3,5]等等其中最短长度是2而[1,2]是所有这些最短区间里左端点最小的所以答案是1 2。题目要求的输出就是两个整数分别是最短区间的左右端点。输入格式也很常规第一行两个整数n和m第二行n个整数表示每幅画的画家编号。n的范围在10^6级别m的范围在2000级别。看到这个数据规模基本就能判断这题的正解必须是O(n)或者O(n log n)任何平方级算法都会超时。1.2 暴力为什么必超时先算清复杂度再动手很多刚开始刷题的同学第一反应是枚举所有区间再统计区间里有没有覆盖全部画家复杂度高得吓人。枚举左右端点本身就是O(n^2)种区间每个区间再统计一下覆盖情况整体到O(n^3)甚至O(n^2*m)都很正常。哪怕做个小小的优化让区间左端点固定时右端点向右扩展顺便把统计信息同步维护复杂度也只能降到O(n^2)。问题就出在n是10^6。10^6的平方是10^12就算你单次操作真的只耗时1纳秒也要10^4秒才能跑完大概三个小时。而在真实竞赛环境下题目时间复杂度要求往往是1秒左右最多给你2到3秒。所以暴力在这道题面前没有任何机会这不是优化不优化的问题是一开始就走错了方向。当你发现题目要求的是连续区间又对区间内部元素的“种类覆盖”有明确约束时第一反应应该就是滑动窗口。这个直觉非常重要刷题刷多了你会发现有一大类题都是这个套路连续区间加计数约束优先考虑双指针能不能做。1.3 滑动窗口的直觉为什么窗口左边缘从不后退滑动窗口能工作的根本原因是一个单调性。我们定义一个函数f(r)表示在所有右端点为r的区间里能够覆盖全部m个画家的最靠右的左端点。注意为了区间尽量短在右端点固定的情况下左端点当然希望越靠右越好但如果左端点太靠右区间就会缺失某些画家所以f(r)其实是在“还能覆盖全部画家”这个约束下左端点能让区间最短的位置。关键结论是当右端点r增大时f(r)是单调不减的。也就是说左端点永远不会向左退回去。这个性质可以很直观地理解右端点向右扩展窗口里的画家种类只可能增加、不可能减少所以之前被排除掉的左端点在新窗口里依然可以保持排除状态而一些之前必须保留的左端点现在反而有机会向右移动了。用生活里的话说想象你在看一排在墙上的画用一个相框去框住它们相框的右边缘向右移动时左边缘只可能跟着向右或者不动绝不会往回退。因为右边缘都往右看了更多画了左边缘当然没有必要退回去。这个单调性就是双指针算法能以O(n)完成扫荡的根本保证。2. 滑动窗口两大核心问题指针怎么动状态怎么记2.1 右指针负责扩张左指针负责收缩滑动窗口的代码逻辑里两个指针的分工非常明确。右指针是“进攻方”每一轮循环都要把一个新的元素纳入窗口左指针是“收敛方”只有在当前窗口已经满足“覆盖全部m个画家”这个条件时才会尝试向右收缩把多余的、不影响覆盖的元素从窗口里踢出去。这里有个顺序问题必须养成肌肉记忆先扩张再收缩。每一轮循环都是先把a[r]加进窗口然后判断当前窗口是否达标达标就尝试收缩。反过来先收缩再扩张是错的——窗口还没覆盖全部画家时收缩没有任何意义而如果你不先扩展就收缩还有可能把cnt计数搞出负数。右指针每轮只走一步这一步没有任何讨价还价的余地因为我们要枚举所有可能的右端点。真正需要动脑子的是左指针怎么收缩、什么时候收缩、收缩到什么程度。这部分做对了整道题就做对了一大半。2.2 用cnt桶和diff变量维护窗口状态窗口状态怎么记录最朴素的想法是每次重新统计区间内每个画家的出现次数但那样每次都O(m)太慢。正确的做法是用一个计数数组cnt配合一个整型变量diff。cnt[x]表示当前窗口内画家x出现了多少次。diff表示当前窗口内出现了多少种不同的画家编号。比如窗口是[1,1,2]cnt[1]2cnt[2]1diff2因为出现了1和2两种。扩展右指针纳入新元素a[r]时如果cnt[a[r]]原本是0说明这个画家第一次进入窗口diff就加1然后无论之前是不是0cnt[a[r]]都要加1。收缩左指针移出元素a[l]时先让cnt[a[l]]减1如果减完之后变成0说明这个画家从窗口里彻底消失了diff就减1。这里不用哈希表或set的原因很简单画家编号范围明确是1到m直接开一个长度为m1的数组每次操作都是O(1)的随机访问常数极小代码也干净。哈希表虽然也能做但每次插入删除都带着哈希计算的额外开销在10^6数据量下虽然不至于超时但没必要。2.3 收缩用while不用if决定成败的细节很多第一次写这道题的同学会把收缩条件写成if (diff m)结果答案总是偏大怎么都想不通。问题在于你收缩一次之后窗口可能依然覆盖全部画家仍然可以继续收缩。比如窗口里画家1出现了3次、画家2出现了2次你从左端移出一个画家1窗口里画家1还剩2次diff还是2窗口依旧达标。这种情况必须继续收缩直到再移出某个元素会导致某种画家归零为止。所以收缩必须用while循环只要窗口依然覆盖全部画家就一直收缩。每次收缩前当前窗口是一个可行解需要先比较更新答案收缩后再进入下一轮判断直到diff不等于m为止。这里还有一个很多题解含糊带过的点答案更新用严格小于还是小于等于。我的习惯是只在长度严格变小时更新r - l ansR - ansL。原因很简单滑动窗口的右端点r从左往右扫描等长的可行区间一定是先出现的那个左端点更小。如果写成小于等于后面出现的等长区间会把左端点更小的旧答案覆盖掉导致输出不符合“左端点最小”的要求。2.4 初始化与循环写法的两个小选择初始化里我最推荐的做法是左指针l从1开始右指针r在for循环里从1遍历到n初始时窗口为空cnt全部为0diff为0。这样每一轮循环的逻辑高度统一先扩展再收缩。不要一开始就把a[1]塞进窗口再从r1开始循环那个写法会让你的first move变得别扭很多边界情况容易漏。答案变量我习惯初始化成ansL1, ansRn对应整个数组。为什么要这么设因为题目保证一定有解但最坏情况下答案有可能就是整个数组长度n-1。初始值设成整个区间后第一个可行解无论如何都能从一个不大于它的长度开始比较而如果最终答案真是整个数组初始值本身就会作为答案输出非常方便。你也可以初始化成ansL0, ansRn1之类的但那个写法要多处理一层“是否已找到答案”的判断没这个简洁。3. 手把手实现完整C代码与逐段解析3.1 数据存储与读入数组开多大怎么读n最大10^6所以原数组a需要至少10^65的空间。m最大2000计数数组cnt开2005就足够。两个数组都用全局变量来定义原因是全局数组分配在静态存储区不受栈大小限制而且会自动清零省得你手动memset。如果你非要用局部数组一不小心就在大数据的评测环境下爆栈了。读入方面直接用scanf是最稳妥的选择。10^6个整数printf和scanf完全扛得住。想用cin也行但一定要先写ios::sync_with_stdio(false); cin.tie(nullptr);否则C流和C标准IO的同步机制会让你白白多花很多时间。我个人更推荐scanf因为省心不用惦记绑定那两个设置。a数组本身需要4MB左右的内存cnt数组不到10KB整体内存开销非常小别说常见的128MB限制就是给你一个8MB的苛刻环境也能轻松跑过。3.2 完整代码可以直接抄的版本#include cstdio const int MAXN 1000005; const int MAXM 2005; int a[MAXN]; int cnt[MAXM]; int main() { int n, m; scanf(%d%d, n, m); for (int i 1; i n; i) { scanf(%d, a[i]); } int l 1; int diff 0; int ansL 1, ansR n; for (int r 1; r n; r) { // 扩张把 a[r] 纳入窗口 if (cnt[a[r]] 0) { diff; } cnt[a[r]]; // 收缩只要当前窗口已经覆盖所有画家 while (diff m) { // 记录当前可行解 if (r - l ansR - ansL) { ansL l; ansR r; } // 把 a[l] 移出窗口 --cnt[a[l]]; if (cnt[a[l]] 0) { --diff; } l; } } printf(%d %d\n, ansL, ansR); return 0; }这段代码可以直接提交到洛谷通过。但如果你只是复制粘贴那就浪费了这篇文章。下面我把核心循环逐行拆开讲一遍确保你明天自己也能写出来。3.3 核心循环逐段拆解先说扩张部分。r循环每次进入一个新元素。if (cnt[a[r]] 0) diff;这一句是在判断这个画家是不是第一次在窗口里出现。如果是不同的画家种数加1。紧接着cnt[a[r]];更新计数。这两条语句的顺序不能颠倒因为必须基于旧状态判断是否新增种类再更新计数。进入收缩部分之前先看一个条件while (diff m)。diff等于m说明窗口已经聚齐了全部画家。这个while循环里做了一个很关键的设计先记录答案再移出元素。很多题解里把答案更新写在收缩完成之后这是有问题的因为收缩过程中间出现的更优区间会被漏掉。想象一个窗口有7个元素左边是多出来的3个冗余元素收缩过程中整个窗口依然覆盖全部画家这时才是真正的“临界最短”而你如果等到while结束才记录窗口已经被收缩到不达标了记录的自然是错误答案。移出元素时先--cnt[a[l]]然后判断减完是否为0。如果变成了0说明这种画家在窗口里彻底消失了diff才减1。这个判断不能省否则diff会在画家种类实际上变少时仍然虚高导致while多收缩甚至收缩到不达标的窗口。最后l把左指针右移一位。关于diff m写成diff m行不行其实由于画家编号最多m种diff理论上不可能超过m所以两者效果完全一样。我写是为了逻辑上更精确这个窗口不多不少刚好覆盖全部画家时才进入收缩流程。3.4 用一组数据走一遍程序模拟全过程我们拿样例5 2数组1 2 1 1 2来手动过一遍。下面的表格里窗口用画家集合表示方便看diff但你心里要知道cnt记录的是每个画家具体出现次数。轮次扩展后窗口diff收缩过程当前最优答案r1{1}1diff1不收缩无r2{1,2}2记录[1,2]删a[1]1窗口{2}diff1[1,2]r3{1,2}2记录[2,3]长度2与[1,2]等长不更新删a[2]2窗口{1}diff1[1,2]r4{1}1diff1不收缩[1,2]r5{1,2}2记录[3,5]长度3不优删a[3]1窗口{1,2}长度2等长不更新再删a[4]1窗口{2}diff1[1,2]注意看r3时的关键窗口[2,3]的内容是画家2和画家1覆盖了m2种画家长度2和答案[1,2]一样长。但由于右端点r3比r2靠右左端点也跟着靠右了从题意要求的“等长输出左端点最小”来看[1,2]比[2,3]更优所以答案保持[1,2]。这正好验证了严格小于更新的必要性。r5的收缩过程特别值得看先记录[3,5]长度3不好收缩一次得到[4,5]内容是画家1和画家2长度2依然达标但等长不更新再收缩一次左边又删掉一个画家1窗口只剩画家2diff变成1循环结束。这一轮把while的多次收缩演示得明明白白。3.5 提交与优化快读要不要用提交的时候建议选C14或C17标准这份代码完全兼容。1秒的时间限制下scanf读10^6个整数完全没问题不需要快读。但如果你想养成一个通用习惯写一个针对正整数的快读模板也很简单用getchar逐字符读入遇到数字就累加。这个习惯在遇到10^6以上大输入、且常数要求极严的题时能帮你省下不少时间。不过针对P1638加上快读属于“锦上添花”不加也完全能过。我自己的习惯是头一次做这道题时不要加任何优化先把朴素的双指针版本写对、调通然后再去考虑快读。先求正确再求效率这个顺序在备考阶段比什么都重要。4. 实战中踩过的坑常见问题与调试技巧实录4.1 五个高频错误与修复方法这道题网上提交记录里最常见的错误翻来覆去就那么几个。我整理成一个表你写代码的时候对着自查一遍。错误写法现象正确做法收缩用if (diffm)答案区间比正确结果偏大改成while (diffm)收缩到不能再缩移出元素时不更新diff收缩后diff虚高窗口不达标也继续收缩--cnt[a[l]]后判断cnt[a[l]]0再--diff收缩结束后才更新答案可能记录到不达标的区间或错过中间最优在while循环内、每次移出元素之前更新答案数组从0开始编号输出时忘记1答案总是比正确值小1统一用1-based下标或者输出时1cnt数组只开到m而不是m1画家编号为m时数组越界cnt开m1甚至更大用MAXM常量一次性定义这里最阴险的是第三个收缩结束后才更新答案。你单步调试的时候可能觉得逻辑没问题因为收缩结束后窗口的状态往往也是某个“看起来合理”的状态但对拍小数据时就会发现答案悄悄偏了。记住一句话只要当前窗口达标它就是候选答案立刻记录。4.2 四组边界数据自测清单写完代码不要急着提交先用几组边界数据自测。我把常用的几组列在这里每一组都在考一个不同的点。测试用例期望输出考察点1 111 1最小规模n和m都等于14 11 1 1 11 1m1时答案就是任意单元素区间左端点最小3 31 2 31 3覆盖全部画家必须用整个数组答案就是整个区间10 31 1 1 2 2 2 3 1 1 14 7右侧扩张很长后左侧连续收缩多次才到临界点最后一组我故意设计成需要“先跑很远再猛收缩”的情况。前三个元素全是画家1然后三个画家2到第7个位置才第一次出现画家3所以第一次达标的窗口是[1,7]。但这个窗口里画家1出现了4次、画家2出现3次左边可以一路收缩掉三个画家1和两个画家2最终得到[4,7]这就是答案。你要是用if收缩这题就错了它会停在某个中间状态或者多收缩一次变成[7,7]导致漏解。4.3 调试技巧让窗口状态可视化我调试这类双指针题最常用的办法是在循环里加临时的输出把每一轮的l、r、diff以及关键cnt值打出来。比如在while循环里加一句printf(l%d r%d diff%d cnt[1]%d cnt[2]%d\n, l, r, diff, cnt[1], cnt[2]);压到小数据上跑一遍窗口的扩张和收缩过程就全在眼前了。一旦发现diff该减没减、该加没加马上就能定位到是哪一步的逻辑问题。这个打印调试法虽然土但对付这类状态维护题效率极高。等你把整道题跑顺了记得把这些调试语句删掉再提交或者用#ifdef LOCAL包起来。还有一个小技巧本地对拍时用文件输入输出。在main函数开头写两句freopen(in.txt, r, stdin); freopen(out.txt, w, stdout);测试数据放文件里程序跑完直接查看输出文件比每次手动敲数据方便得多。提交前把这两句注释掉别带进评测系统。5. 从一道题到一类题滑动窗口模板与备考冲刺建议5.1 滑动窗口的通用模板刷完P1638最有价值的收获取舍是提炼出一个可以反复套用的滑动窗口模板。这个模板不只是写代码的框架更是一套思考步骤。第一步识别题型题目要求在一个连续子数组或子串上做统计并且给出了某种计数约束。第二步明确指针含义右指针枚举区间右端点左指针在区间达标后向右收缩。第三步设计状态表示用一个数组对应“窗口内出现次数”用一个数据变量对应“种类数”或者其他需要维护的指标。第四步想清楚收缩条件和答案更新位置。模板伪代码像一个固定剧本右端点r遍历整个序列: 把a[r]加入窗口更新状态 当窗口满足题目约束: 记录当前窗口作为候选答案 把a[l]移出窗口更新状态 l 1这个模板能直接迁移的题非常多。你以后遇到任何“求最短区间满足XXX”“求最长区间满足XXX”的题都可以先往这个模板上靠。差别只在于“状态”怎么设计、“约束条件”怎么判断骨架是不变的。5.2 同类题扩展清单把模板迁移出去在LeetCode上一搜滑动窗口的经典题一大把和P1638相似度最高的是76题“最小覆盖子串”它要求找到字符串s中能覆盖字符串t全部字符的最短子串。本质和逛画展几乎一模一样区别只在于画家编号是整数而这里字符集是字母画家要求覆盖1到m种这里要求覆盖t串中每个字符至少一次P1638统计的是“种类数diff”最小覆盖子串要统计的是“目标字符全部满足的数量”。把cnt数组从int换成字符索引把diff换成“满足条件的字符种数”代码框架完全不动。再往下扩展第3题“无重复字符的最长子串”考的是窗口内某个字符出现次数不能超过1第209题“长度最小的子数组”考的是窗口内数字和大于等于target第438题“找到字符串中所有字母异位词”考的是窗口内各字符计数恰好和模式串一致。这些题从双指针的视角看都是在同一个模板上改状态定义和收缩条件。你在洛谷刷题单里也会反复看到这类题比如前缀和和双指针常常搭配出现。练的时候不用贪多每天挑1到2道把模板套进去写的过程中思考“这题和上一题的状态定义差在哪里”比闷头刷十道题更高效。5.3 冲刺期刷题建议把一题榨干临近竞赛的冲刺阶段我不建议再去啃那些偏题怪题。像P1638这种基础模型题恰恰是考场上最值得依赖的得分点。我的建议是三步走。第一步限时15到20分钟独立完成这道题不看题解不看这篇博文写完提交。第二步过一天再写一遍这次目标是保证一次通过、不调试。第三步过一周再写一遍并用它给同学讲一遍思路。能讲明白才是真的掌握。如果你能把一个双指针模板讲到别人听懂考场上遇到变形题你基本不会慌。另外把所有高频模板整理成一个小抄很有用。滑动窗口的模板要点、二分答案的判断函数怎么写、前缀和的典型应用每类写几行核心代码考前翻一遍比你临时抱佛脚刷几十道题有效得多。P1638这类题就非常适合作为双指针模板占在小抄第一行。最后说一个我实际带选手时的小经验。很多同学觉得自己双指针学会了但一到考场上写出来的代码还是缩不对。问题通常出在“手脑不一”嘴上说着收缩到不达标为止手上写的却是一遍if。所以每次写完滑动窗口题我会强迫自己刻意检查那个while关键字。一个while就是这类题最容易丢分的地方也是你从“看懂题解”走向“独立AC”的分水岭。