一、定义双指针算法是一种在数组、链表等线性数据结构中常用的技巧。它通过使用两个指针移动来完成搜索、判断或变换等操作核心目的是降低时间复杂度通常从 O(n²) 优化到 O(n)。二、双指针的基本类型对撞指针两个指针分别指向数组的头和尾向中间移动。同向指针两个指针从同一端出发但移动速度不同。滑动窗口实际上是快慢指针的一种变体两个指针维护一个窗口。三、例题最长连续不重复子序列题目描述题目来源于AcWing---属于滑动窗口类型思路遍历数组对于每一次遍历把对应数出现的次数加1。当区间内出现重复元素时收缩区间出现的重复元素必定时新添入的数a[i]是因为这个数的出现次数大于1。将左区间减小对应边界的数的次数减1.。将区间边界一直往右移动知道区间内元素不再重复。更新区间长度并输出结果。代码#includeiostream using namespace std; const int N 1e6 10; long long n; //a数组用来存储输入的数据s数组表示每个数出现的次数 long long a[N], s[N]; int main(){ cinn; //输入数据 for(int i 0; i n; i){ cina[i]; } int res 0; //双指针算法---求无重复元素的区间 for(int i 0, j 0; i n; i){ //遍历一个新的数据时次数加1 s[a[i]]; //当区间[j,i]内有重复元素时对应的次数大于1------缩小区间范围(减少次数更新指针位置) while(j i s[a[i]] 1){ s[a[j]]--; j; } //更新区间长度 res max(res, i - j 1); } cout res endl; return 0; }逛画展题目描述题目来源于洛谷---属于滑动窗口类型思路遍历输入的所有编号。如果画家编号没有出现过则画家个数加1。对应画家出现的次数加1。当区间内包括所有的画家时开始收缩区间。如果区间的右边界小于数据的最大边界更新区间左右边界。如果区间长度小于数据整体长度且区间左边界大于数据最左边更新区间左右边界。更新边界之后将对应画家出现的次数减1。判断画家是否出现在区间如果没出现则画家个数减1。输出左右边界。代码#includeiostream using namespace std; const int N 1e6 10; long long n, m; long long a[N], s[N]; int main(){ cinnm; //输入数据 for(int i 0; i n; i){ cina[i]; } //记录x,y,cnt----cnt表示当前窗口出现的画家的个数 long long cnt 0; long long res_x 1, res_y n, res_len n 1; //使用双指针算法 for(int i 0, j 0; i n; i){ //如果画家之前没有出现过则画家个数加1 if(s[a[i]] 0){ cnt; } //对应画家出现的次数加1 s[a[i]]; //当画家个数m时收缩区间 while(cnt m j i){ long long len i - j 1; if( i res_y || (len res_len j res_x)){ //更新区间边界 res_x j; res_y i; res_len len; } //更新画家出现的次数 s[a[j]]--; //判断画家是否还在区间中出现过 if(s[a[j]] 0){ cnt--; } j; } } //输出x,y cout res_x 1 res_y 1endl; return 0; }数组元素的目标和题目描述题目来源于AcWing---属于对撞指针类型思路使用两个数组a,b存储输入的数。数组a的指针从左往右遍历,数组b的指针从右往左遍历。如果a[i] b[j] x 且 j 0,则数组b的指针左移一位。如果a[i] b[j] x输出 i 和 j 的值。每次遍历结束后i.代码#includeiostream using namespace std; const int N 1e5 10; long long n, m, x; long long a[N], b[N]; int main(){ cinnmx; //输入数组a for(int i 0; i n; i){ cina[i]; } //输入数组b for(int i 0; i m; i){ cinb[i]; } //使用双指针算法计算i,j for(int i 0, j m - 1; i n; i){ //i指针从左往右j指针从右往左 while(a[i] b[j] x j 0){ j--; } if(a[i] b[j] x){ cout i j endl; break; } } return 0; }判断子序列题目描述题目来源于AcWing---属于同向双指针类型思路使用a,b数组存储输入的两组数据。从左往右遍历两个数组。如果a[i] b[j] ,则 i每次遍历时j.如果最后 i 的值等于n则输出yes,否则输出no.代码#includeiostream using namespace std; const int N 1e5 10; long long n, m; long long a[N], b[N]; int main(){ cinnm; //输入数组 for(int i 0; i n; i){ cina[i]; } for(int i 0; i m; i){ cinb[i]; } int i 0, j 0; //同向双指针 while(i n j m){ if(a[i] b[j]){ i; } j; } if(i n){ coutYesendl; }else{ coutNoendl; } return 0; }四、总结每次使用双指针算法时可以先想暴力算法怎么求解再对其进行优化。双指针算法通常可以把O()的时间复杂度优化到O(n)。