用于枚举优化的同向双指针

2026.3.20 优化部分LaTex公式

双指针思想

双指针算法有时候也叫尺取法、滑动窗口或同向双指针，是一种优化暴力枚举策略的手段。

当我们发现在两层for循环的暴力枚举过程中，两个指针或两个起到指针作用的变量是可以不回退的，此时我们就可以利用两个指针不回退的性质来优化时间复杂度。

因为双指针算法中，两个指针是朝着同一个方向移动的，因此也叫做同向双指针。

唯一的雪花 双指针的思考过程

UVA11572 唯一的雪花 Unique Snowflakes - 洛谷

这是一道UVA的题，UVA是国外的OJ网站，只有先在UVA注册账号，并绑定洛谷账号才能在洛谷上提交。

如果无法注册，可以在Virtual Judge注册，通过这里来提交。

这个题的题目并不容易读懂，需要理解作者想要我们做什么。

不包含两片一样的雪花的包裹最大能有多大：注意关键词包裹，题目要求输出包裹的大小，根据题解也能看出最长的包裹是[1,2,3]，联想到数组的长度。

她可以在任何时候启动机器，但是一旦机器启动了，直到包裹被封上为止：选择的雪花是数组中连续的部分。

所以，这题经过二次翻译后就是：给你T组数据，每组数据告诉数组的长度和元素，问其中连续且两两不同的子序列的最长长度。

根据翻译，样例[1,2,3,2,1]可选的序列有[1,2]，[3,2,1]等，最长的是[1,2,3]和[3,2,1]。

可以尝试暴力枚举：枚举出所有符合要求的子数组，找出最长的那个。最容易想到的是两层循环，第一层固定起点位置，第二层枚举后续的所有元素来选出结尾的元素。

知道思路之后，还需要知道新加入结尾的元素是否有重复，这点可以通过哈希表或键值对来查重。每个新元素在哈希表中查不到时，便加入哈希表；若查得到，则记录当前的最大长度。

但所有的数组元素数是10 6 10^6106，用两层循环的话循环次数是10 12 10^{12}1012，所以肯定超时，需要优化。

从枚举的原理分析：

通过对暴力枚举的研究发现性质：L和R两个起到下标作用的指针可以不用回退。

所以这个题可以用同向双指针。具体分析思路：

1. 初始化。
   （如何进行同向双指针的操作？）定义一个L=0和R=0两个指针，全部指向起始位置。

   （用什么结构维护窗口，即L到R之间的数据的信息？）例如这题的一个区间：[1,2,3,4,5]，考虑到窗口内所有元素俩俩不同，可以用双关键字的哈希表unordered_map，关键字这样定义：
   <元素，元素出现的次数>，例如当[L,R]维护的窗口变成[1,2,3,4,5,3]时，因为最后1个3加入哈希表时发现3重复，此时窗口不合法。
   所以针对这题，双指针的初始化要做的任务是给两个指针和哈希表。

2. 进窗口。
   即让R指向的元素进入窗口。如果是哈希表，则mp[a[R]]++;

3. 判断。
   即判断窗口是否合法。这里的窗口合法建立在窗口中元素俩俩互不相同，这里只有通过R加入窗口的元素才能造成窗口不合法，所以做判断mp[a[R]]>1。

4. 出窗口。
   若表达式mp[a[R]]>1为真，则说明窗口不合法，需要执行出窗口的操作：L右移，使L指向的元素出窗口，直到窗口合法，即mp[a[L]]--。
   所以这里的判断和出窗口的操作是一个完整的循环。

5. 更新结果。
   （需要根据题意判断怎样更新结果）有时更新结果是在循环的判断内，有时是出窗口的任务全部结束后再更新。
   这里是窗口合法后再更新。例如给个变量ret，ret=max(ret,R-L+1)。

这5个步骤是同向双指针的思考过程，具体应用时需要根据题意来设计窗口。但要先考虑一个暴力解法，再根据这个暴力解法中是否出现性质双指针不回推，此时才能使用同向双指针的分析思路解决问题。

为什么滑动窗口是正确的？

在指针移动的过程中，R无论是否回到L重新移动都会回到使窗口非法的位置，所以滑动窗口规避了很多没必要的枚举。例如这个OJ。

因为暴力枚举本身就是将所有可能的情况枚举一遍，只要需求和问题不是有特别大的歧义，本身就是正确的。滑动窗口作为枚举的优化，肯定也是正确的。

时间复杂度？

例如本题，看似两个循环，因为指针不回退，最差情况下两个指针L和R会各自遍历一次数组，所以枚举次数其实是n + n n+nn+n，时间复杂度其实是O ( n ) O(n)O(n)。

参考程序：

#include<bits/stdc++.h>// 在MSVC中，哈希表并不在标准c++头文件中#include<unordered_map>usingnamespacestd;constintN=1e6+10;intn,a[N];intmain(){intT;cin>>T;while(T--){cin>>n;for(inti=1;i<=n;i++)cin>>a[i];// 初始化intL=1,R=1;// 需要根据数组的起始下标初始化intret=0;unordered_map<int,int>mp;// 维护窗口内所有元素的出现次数while(R<=n){// 进窗口mp[a[R]]++;// 判断while(mp[a[R]]>1){// 出窗口mp[a[L]]--;L++;}// 窗口合法，更新结果ret=max(ret,R-L+1);R++;// 让循环能进行}cout<<ret<<endl;}return0;}

做类似的题时，开始并不能知道这个题能用滑动窗口解决，如果那个题除了题干、输入和输出，其他啥都没给，能做的是利用自己的知识储备，尝试用各种已经学过的算法来解决。

例如滑动窗口，若题目出现两层循环的暴力枚举存在理论的解决问题的可能，则观察两层循环的两个指针作用的变量是否可以不回退，若满足这些条件，则可以利用滑动窗口优化。这题用的是哈希表，别的题可能是一个变量，或别的数据结构。

逛画展 在窗口合法的情况下寻找最优解

P1638 逛画展 - 洛谷

P1638 逛画展 - 洛谷

这题大概的意思是选一段连续子序列，这个子序列覆盖了[1,m]的所有数字。

和雪花一样，首先想到的是两层循环的暴力枚举，循环次数是10 12 10^{12}1012，铁定有样例超时。然后发现两个指针没有回退的必要，于是想到使用双指针。

双指针的思考方式：

1. 初始化
   定义L和R两个指针，用unordered_map定义一个哈希表mp，两个记录最终结果的变量ll和rr。
2. 进窗口
   让R指向的元素进入窗口（mp[a[R]]++）。
3. 判断
   首先判断mp是否覆盖了[1,m]的所有数字，若覆盖了则进行出窗口操作，试图压缩这个窗口的长度。
   这一步用了一步贪心策略：即在保证覆盖了[1,m]的所有数字的情况下，不断缩小窗口的长度来寻找最优解。
   也就是说，mp没有覆盖m个数字的情况下窗口都不合法，需要不停地进窗口来使窗口合法。这里的滑动窗口也和别的滑动窗口不一样，别的滑动窗口是判断不合法时才出窗口，这里是在合法的条件下通过出窗口来寻找最优解。
4. 出窗口
   同样是先判断mp是否覆盖了[1,m]的所有数字，若覆盖了则通过mp[a[L]]--出窗口，并使L指针后移。
5. 更新结果
   若窗口合法，且找到了长度更小的子序列则更新结果ll和rr。

但这题和唯一的雪花的不同点是，做判断和出窗口的前提是窗口整体合法，例如维护窗口的哈希表保存了指定数量的元素。

P1638 逛画展 - 洛谷参考程序：

#include<bits/stdc++.h>#include<unordered_map>usingnamespacestd;/* https://www.luogu.com.cn/problem/P1638 */intmain(){vector<int>a;intn,m;cin>>n>>m;a.resize(n+1,0);for(inti=1;i<=n;i++)cin>>a[i];//滑动窗口初始化intL=1,R=1,ll=0,rr=0,len=0x3f3f3f3f;unordered_map<int,int>mp;while(R<=n){//进窗口mp[a[R]]++;//判断while(mp.size()>=m&&mp[a[L]]>1){//在窗口合法的情况下出窗口mp[a[L]]--;L++;}//窗口合法的情况下更行结果if(mp.size()>=m&&len>R-L+1){len=R-L+1;ll=L;rr=R;}//让循环能进行R++;}cout<<ll<<' '<<rr;return0;}

当然，这个题方法比较多，肯定不止局限于滑动窗口。这里不再枚举。

字符串 Nowcoder

字符串

和逛画展差不多。但窗口合法的条件是哈希表的长度是26个字母。

#include<bits/stdc++.h>#include<unordered_map>usingnamespacestd;intmain(){string st;cin>>st;intL=0,R=0;unordered_map<char,int>mp;intlen=st.size();while(L<=R&&R<st.size()){mp[st[R]]++;while(mp.size()>=26&&mp[st[L]]>1){mp[st[L]]--;L++;}if(mp.size()>=26&&len>R-L+1)len=R-L+1;R++;}cout<<len;return0;}

丢手绢 无论窗口是否合法都要更新结果

丢手绢 Nowcoder

丢手绢

首先，根据题意得出距离的定义：假设x xx走向y yy的顺时针上的距离为m mm，逆时针上的距离为k kk，则x xx与y yy的距离为min(k,m)。

针对第i个人，如何找出距离i最远的那个人，那个人和i的距离是多少，只要能解决这个问题，就能解决这题。

而这个人可能有两个，一个是顺时针方向的最远，另一个是逆时针方向的最远，也有可能两个方向一样远。

假设从a[i]号人开始顺时针看，将沿途经过的所有人的顺时针距离相加，若第一次遇到一个人a[j]，这个人离最开始的那个人的距离≥ S u m 2 \geq \frac{Sum}{2}≥2Sum​（S u m SumSum是所有距离的总和，也可以认为是这个环形的周长），此时可以得出结论，a[j-1]就是离a[i]在顺时针方向上最远的人。再计算a[j]的距离时只能用逆时针来运算（因为顺时针的距离≥ S u m 2 \geq \frac{Sum}{2}≥2Sum​），且a[j]就是离a[i]在逆时针方向上最远的人。

此时可以用枚举来尝试解决：暴力枚举出所有的人距离别人的最远距离，在所有情况下取max即可。

这时可以定义两个变量L和R，当∑ i = L R a i ≥ S u m 2 \sum\limits_{i=L}^Ra_i\geq \frac{Sum}{2}i=L∑R​ai​≥2Sum​时，枚举停止，距离为min ⁡ ( ∑ i = L R − 1 a i , S u m − ∑ i = L R a i ) \min (\sum\limits_{i=L}^{R-1}a_i,Sum-\sum\limits_{i=L}^{R}a_i)min(i=L∑R−1​ai​,Sum−i=L∑R​ai​)。所以可以用两层循环来枚举，时间复杂度为O ( n 2 ) O(n^2)O(n2)，不出意外的话肯定超时。此时需要优化暴力解法，先看有L和R是否出现回退的情况。如图所示：

根据图中的信息，当R走到4时a[1]+a[2]+a[3]>=Sum/2, 传统的暴力做法是L从1移动到2，R回退到2重新开始计算。

但其实R没有回退的必要，因为L从1移动到2时，L和R的顺时针方向的距离在减小， 即L和R的距离是a[2]+a[3]。 为了找到大于Sum/2的情况，R需要在L移动时通过顺时针移动来维持这个距离。

也有可能L移动时距离依旧大于Sum/2，所以R有时也不移动 。

所以R没有回退的必要。根据这个特性，可以用滑动窗口解决。

1. 初始化
   初始化变量L、R和dis=0，以及记录最终结果的变量res。
2. 进窗口
   dis+=a[R]。
3. 判断
   当2*dis>=Sum时，此时窗口不合法，需要出窗口。判断和出窗口组成一个循环。
4. 出窗口
   k-=a[L]。
5. 更新结果
   窗口合法（即2*dim<Sum）时更新结果，此时需要用∑ i = L R a i \sum\limits_{i=L}^{R}a_ii=L∑R​ai​即顺时针的距离更新结果。
   而当窗口不合法时，也要用S u m − ∑ i = L R a i Sum-\sum\limits_{i=L}^{R}a_iSum−i=L∑R​ai​更新结果，因为从L到R+1的逆时针方向的距离也可能是最终结果。
   因此这个题更新结果需要在两个位置。

参考程序：

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;intmain(){intn;cin>>n;vector<int>a(n+1,0);intsum=0;for(inti=1;i<=n;i++){cin>>a[i];sum+=a[i];}//初始化intL=1,R=1,dis=0,res=0;while(L<=R&&R<=n){//进窗口dis+=a[R];//判断while(2*dis>=sum){//用逆时针方向的距离更新结果res=max(res,sum-dis);//出窗口dis-=a[L++];}//用顺时针方向的距离更新结果res=max(res,dis);R++;}cout<<res;return0;}

OJ 汇总

UVA11572 唯一的雪花 Unique Snowflakes - 洛谷

P1638 逛画展 - 洛谷

字符串

丢手绢