概念
双指针，顾名思义，就是用两个指针解决问题。
有些问题用单指针会出现超时等问题，这时就需要用到双指针
双指针由两个指针组成，一般是左右指针，或前后指针
通过两个指针配合变化，用更短的时间高效解决问题
题目
（续上一篇，如需了解上一篇题目，请移步主页观看）
合并有序数组
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int la,lb,lab;
int a[20010],b[10010];
int main()
{
cin>>la;
for(int i = 1;i<=la;i++)
{
cin>>a[i];
}
cin>>lb;
for(int i = 1;i<=lb;i++)
{
cin>>b[i];
}
lab = la+lb;
int ai = la+1,bi = lb+1,abi = lab+1;
while(ai>1&&bi>1)
{
if(a[ai-1]>b[bi-1]) a[–abi] = a[–ai];
else a[–abi] = b[–bi];
}
while(bi>1) a[–abi] = b[–bi];
for(int i = 1;i<=lab;i++) cout<<a[i]<<" ";
return 0;
}
完美数列
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,p;
int a[10010];
int main()
{
cin>>n>>p;
for(int i = 1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+n+1);
int fast = 0,slow = 1;
int ma,mi;
mi = a[slow];
int mama = -999999999;
while(fast<n)
{
while(fast<n)
{
ma = a[++fast];
int x = mi*p;
if(ma<=x) mama = max(mama,fast-slow+1);
else break;
}
while(slow<fast)
{
mi = a[++slow];
int x = mi*p;
if(ma<=x)
{
mama = max(mama,fast-slow+1);
break;
}
}
}
cout<<mama;
return 0;
}
反转元音字母
#include <bits/stdc++.h>
#define ll long long
using namespace std;
string a;
char yy[] = {'a','e','i','o','u'};
int main()
{
cin>>a;
int n = a.size();
int l = 0,r = n-1;
while(l<r)
{
bool lf = false;
bool rf = false;
for(int i = 0;i<5;i++)
{
if(a[l]==yy[i]) lf = true;
if(a[r]==yy[i]) rf = true;
}
if(lf==false) l++;
if(rf==false) r–;
if(lf==true&&rf==true)
{
swap(a[l],a[r]);
l++;
r–;
}
}
cout<<a;
return 0;
}
验证回文串2
#include <bits/stdc++.h>
#define ll long long
using namespace std;
string a;
int n;
bool chushi();
bool hou(int,int);
int main()
{
cin>>a;
n = a.size();
if(chushi()==true) cout<<"true";
else cout<<"false";
return 0;
}
bool chushi()
{
int l = 0,r = n-1;
while(l<r)
{
if(a[l]==a[r]) l++,r–;
else
{
if((hou(l+1,r)|hou(l,r-1))==true) return true;
else return false;
}
}
return true;
}
bool hou(int l,int r)
{
while(l<r)
{
if(a[l]==a[r]) l++,r–;
else return false;
}
return true;
}
最接近的三数之和
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,a[10010],target,misum,micha;
int main()
{
micha = 999999999;
cin>>n;
for(int i = 1;i<=n;i++)
{
cin>>a[i];
}
cin>>target;
sort(a+1,a+n+1);
for(int i = 1;i<=n-2;i++)
{
int l = i+1,r = n;
while(l<r)
{
int sum = a[l]+a[i]+a[r];
int cha = sum-target;
if(cha<0) cha = target-sum,l++;
else r–;
if(cha<micha)
{
micha = cha;
misum = sum;
}
}
}
cout<<misum;
return 0;
}
三数之和的多种可能
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n,a[10010],target;
int cnt;
int main()
{
cin>>n;
for(int i = 1;i<=n;i++)
{
cin>>a[i];
}
cin>>target;
sort(a+1,a+n+1);
for(int i = 1;i<=n-2;i++)
{
int l = i+1;
int r = n;
while(l<r)
{
int sum = a[i]+a[l]+a[r];
if(sum==target)
{
cnt++;
//cout<<cnt<<" "<<i<<" "<<l<<" "<<r<<" "<<a[i]<<" "<<a[l]<<" "<<a[r]<<endl;
int p = r-1;
while(a[p]==a[r]&&p>l)
{
cnt++;
p–;
//cout<<cnt<<" "<<i<<" "<<l<<" "<<p<<" "<<a[i]<<" "<<a[l]<<" "<<a[p]<<endl;
}
l++;
}
if(sum>target) r–;
if(sum<target) l++;
}
}
cout<<cnt;
return 0;
}
