@
目录双指针
基本介绍
双指针主要用于处理数组或链表等线性数据结构中的问题。它的基本思想是使用两个指针（通常是两个变量）来遍历或操作数据，这两个指针可以指向数组的开始和结束位置，也可以根据具体问题指向其他位置。双指针算法能够有效地减少时间复杂度，特别是在处理排序数组或需要查找特定条件下的元素时非常有用。
应用场景
两数之和：给定一个已排序的数组和一个目标值，找出数组中两个数，使它们的和为给定的目标值。可以通过设置一个指针从数组的开始位置，另一个指针从数组的末尾开始，向中间移动，直到找到满足条件的两个数或两个指针相遇。
移除元素：例如，在数组中移除所有出现的某个特定值，并返回新数组的长度。可以使用快慢指针的方法，快指针用于遍历整个数组，慢指针用于记录非移除元素的位置。
合并两个有序数组：将两个已排序的数组合并成一个新的有序数组。可以同时从两个数组的开头或结尾开始，比较元素大小并按顺序放入新的数组中。
链表相关问题：如判断链表是否有环、寻找链表的中间节点等。可以使用快慢指针，其中快指针每次移动两个节点，慢指针每次移动一个节点。
例题
A-B数对
题目链接: A-B数对
题目描述
给出一串正整数数列以及一个正整数 C，要求计算出所有满足 A - B = C 的数对的个数（不同位置的数字一样的数对算不同的数对）。
思路： 枚举左端点l，维护两个右端点r1，r2。具体实现看代码吧！
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 9;
int a[N];
void solve()
{
//输入数据
int n,c;
cin>>n>>c;
for(int i=1;i<=n;i++) cin>>a[i];
//排序 后面枚举左右端点时要保证a[r]>=a[l]
sort(a+1,a+1+n);
//左右端点
int l=1,r1=1,r2=1;
ll ans=0;
for(l=1;l<=n;l++)
{
while(r1<=n&&a[r1]-a[l]<=c) r1++;
while(r2<=n&&a[r2]-a[l]<c) r2++;
//[r2+1,r1]区间满足A-B=C
ans+=r1-r2;
}
//输出答案
cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int _ = 1;
//cin >> _;
while (_--) solve();
return 0;
}
排列排序
题目链接: 排列排序
题目描述
给你一个长度为 n 的排列 p1,p2, ...... ,pn。你需要把它排序。
每次可以花区间长度，即 r-l+1 的代价，选择排列中的任意一段区间 [l,r]，并将 [l,r] 从小到大排序。
现在你可以让他进行若干次这个操作，直到 p 中元素的值从 1 到 n 按升序排序，即对于 1 到 n 的每一个 i，都有 pi=i。
求问花的代价最少为多少？
思路： 首先对于a[ i ] = i 的数据，说明它处于正确的位置，不用进行排序。然后对于不满足的数据进行排序，双指针左右端点 l ，r 。l之前的元素全部都已经到了正确的位置。 此时我们要维护区间 [ l , r ] 的最大值mx，左端点 l 不动，当满足 mx > r 时右端点往右移，最终状态为 mx = r 。然后对区间 [ l , r ] 进行排序，直到 l = n 时结束。
看代码吧！
代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 9;
int n,a[N];
void solve()
{
//输入数据
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
int ans=0;
//双指针
int l=1,r=1;
while(l<=n)
{
//如果某个元素值与下标相同，则元素处于正确的位置，不用进行排序，左指针l加一
if(a[l]==l) l++;
//不相同，则需要进行排序
else
{
//维护区间[l,r]的最大值
int mx=a[l];
int r=l+1;
mx=max(mx,a[r]);
while(mx>r)
{
r++;
mx=max(mx,a[r]);
}
//此时mx=r，对区间[l,r]进行排序
//更新l和ans
ans+=r-l+1;
l=r+1;
}
}
//输出答案
cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int _ = 1;
//多组数据输入
cin >> _;
while (_--) solve();
return 0;
}
总结
- 在使用双指针之前，确保对问题的理解足够深入，明确指针的初始位置、移动规则以及停止条件。
- 对于不同类型的双指针问题（如快慢指针、相向而行的指针等），要灵活选择合适的策略。
- 注意边界条件的处理，避免出现数组越界等错误。