学术计划VOL.2 双指针！

Stars_Seeker

2025-10-12 20:30:41

发布于：重庆

68阅读

0回复

0点赞

双指针！

前言：

这是Stars_Seeker推出的学术计划系列的第二期，希望这个系列能够帮助到刚学习 C++ 或者复习 C++ 却不知道复习哪些的同学们，同时这个系列没有过多的言语和绝美的佳句~~作者语文不好（~~，只有透彻又不完全透彻的知识awa。
~~写的这么差的帖子肯定是AI（~~

双指针是什么

双指针可以看做对于枚举的一种优化。
对于两个指针如果分别从 1 到 n 枚举，那么两重循环嵌套，复杂度是 O(n^2),
但在一些具有单调性的题目中，可以使 i 指针和 j 指针都只需要从 1 到 n 遍历一次，复杂度分别为 O(n) , 总复杂度也是 O(n) 。

例题 1: P1147 连续自然数和
思路：构建前缀和数组，由于数字都大于 0，那么前缀和数组存在单调性，可以考虑双指针 i 指针移动时候，为了使得区间和仍然接近 n，j 指针只会向右移动，因此 i 指针和 j 指针都只需要从 1 到 n 遍历一次，复杂度分别为 O(n) , 总复杂度也是 O(n) 。
代码实现

#include<bits/stdc++.h>
using namespace std;
long long n,s[1145141];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        s[i]=s[i-1]+i; //递推构建前缀和数组
    }
	for(int i=1,j=1;i<=n;i++){ //i每次往右移动一格
    	while(j+1<=n&&s[j+1]-s[i-1]<=n){//找到符合条件的最大的j  
			j++; 
		}  
        //条件为 [i, j] 的区间和小于等于n   
        if(j<=i){
			break; //因为需要最少两个数字  所以 j <= i事后可以直接break
		}
        if(s[j]-s[i-1]==n){
			cout<<i<<" "<<j<<endl; //检查符合条件那么输出
		}
    }
    //完美的结束（
}

例题 2: P1102 A-B 数对
思路：先排序使得数组存在单调性，然后 i 指针从 1 到 n 扫一遍，复杂度为 O(n) , 每次找到符合条件的最大的 j ，将对应的数量加入答案，为了了解当前的 j 是同类数字里出现的第几个数字，可以另外开一个 cnt 数组来记录。为了保持 j 指针尽量大并且满足 a[i] - a[j] >= c ，当 i 指针向右移动时候, j 指针只会不变或者向右移动，那么 j 指针的总移动次数也是 O(n) 。
代码实现

#include<bits/stdc++.h>
using namespace std;
int n,a[114514],cnt[1145141];
int main(){
    int c;
    cin>>n>>c;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
	}
    sort(a+1,a+1+n); //创造单调性
    for(int i=1;i<=n;i++){
        cnt[i]=1;
        if(a[i]==a[i-1]&&i>1){//记录出现的是第几个 
			cnt[i]=cnt[i-1]+1;
		}
    }
    long long ans=0; //可能会爆 int 
    for(int i=1,j=1;i<=n;i++){
            while(j<i&&a[i]-a[j+1]>=c){
				j++; //保证j的位置小于等于 i,寻找符合条件的j的最大值
			}
            //想要的条件是 a[i] - a[j] >= c，在此基础上 j越大，越接近c
            if(a[i]-a[j]==c){
				ans+=cnt[j]; //刚好是c就加入到答案里
			}
    }
    cout<<ans<<endl;
    //完美的结束*2（
}