----双指针(尺取法)
1.找出指定和的整数对----p37(书页)
哈希表
#include<bits/stdc++.h>
using namespace std;
int a[100010];
int main()
{
ios::sync_with_stdio(false);cin.tie();cout.tie();
unordered_map<int,bool>q;
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{cin>>a[i];q[a[i]]=true;}
for(int i=1;i<=n;i++)
{
int x=m-a[i];
if(q[x]{cout<<a[i<<''<<x<<endl;q[x]=false,q[a[i]]=false;}
}
return 0;
}
双指针(尺取法---反向扫描)
#include<bits/stdc++.h>
using namespace std;
int a[100010];
int main()
{
ios::sync_with_stdio(false);cin.tie();cout.tie();
unordered_map<int,bool>q;
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n);
int l=1,r=n;
while(l<r)
{
if(a[l]+a[r]<m)
l++;
else if(a[l]+a[r]>m)
r--;
else {cout<<a[l]<<' '<<a[r]<<endl;l++,r--;}
}
return 0;
}
二分
#include<bits/stdc++.h>
using namespace std;
int a[100010];
bool vis[1000000000];
int main()
{
ios::sync_with_stdio(false);cin.tie();cout.tie();
//unordered_map<int,bool>q;
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
int x=m-a[i];
int g=lower_bound(a+1,a+1+n,x)-a;
if(g>=1&&g<=n&&!vis[a[i]]&&a[i]+a[g]==m)
{cout<<a[i]<<' '<<a[g]<<endl;vis[x]=true;}
}
return 0;
}
双指针(尺取法---同向扫描)
2.判断回文串-------p38
stl大法好(reverse翻转判断)
#include<bits/stdc++.h>
using namespace std;
int a[100010];
bool vis[1000000000];
int main()
{
ios::sync_with_stdio(false);cin.tie();cout.tie();
int t;
cin>>t;
while(t--)
{
string a,b;
cin>>a;
b=a;
reverse(a.begin(),a.end());
if(a==b)cout<<"yes\n";
else cout<<"no"<<endl;
}
return 0;
}
双指针(反向扫描)
#include<bits/stdc++.h>
using namespace std;
int a[100010];
bool vis[1000000000];
int main()
{
ios::sync_with_stdio(false);cin.tie();cout.tie();
int t;
cin>>t;
while(t--)
{
string a;
cin>>a;
int l=0,r=a.size()-1;
bool df=true;
while(l<r)
{
if(a[l]!=a[r])
{cout<<"no\n";df=0;break;}
else l++,r--;
}
if(df)
cout<<"yes\n";
}
return 0;
}
3.寻找区间和----p39
双指针(快慢指针---同向扫描)
#include<bits/stdc++.h>
using namespace std;
int a[100010];
//bool vis[1000000000];
int main()
{
ios::sync_with_stdio(false);cin.tie();cout.tie();
int n,m;
cin>>n>>m;
for(int i=0;i<=n-1;i++)cin>>a[i];
// sort(a+1,a+1+n);
int l=0,r=0,sum=a[0];
while(r<n)
{
//int sum=a[l]
if(sum>=m)
{
if(sum==m)cout<<l<<' '<<r<<endl;
sum-=a[l];
l++;
if(l>r){sum=a[l];r++;}
}
else
{
r++;sum+=a[r];
}
}
return 0;
}
4.多指针
找相同数对----p41
1.哈希法unordered_map
#include<iostream>
using namespace std;
long long n,c,cnt;
#include<unordered_map>
unordered_map<int,int>p;
int a[300000];
int main()
{
ios::sync_with_stdio(false);cin.tie();cout.tie();
cin>>n>>c;
for(int i=1;i<=n;i++){cin>>a[i];p[a[i]]++;}
for(int i=1;i<=n;i++)
{
int x=a[i]+c;
if(p[x])cnt+=p[x];
if(x==a[i])cnt--;
// cout<<cnt<<endl;
// cout<<cnt<<endl;
}
cout<<cnt;
return 0;
}
2.多指针
//三指针区间算法
#include<bits/stdc++.h>
using namespace std;
long long n,c,cnt;
#include<unordered_map>
//unordered_map<int,int>p;
int a[4000000];
int main()
{
ios::sync_with_stdio(false);cin.tie();cout.tie();
cin>>n>>c;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+1+n);
for(int i=1,j=1,k=1;i<=n;i++)
{
while(a[j]-a[i]<c&&j<=n)j++;//不能等号因为最后一次j+会使得a[j]-a[i]>=c
while(a[k]-a[i]<=c&&k<=n)k++;
if(a[j]-a[i]==c&&a[k-1]-a[i]==c&&k-1>1)cnt+=k-j;//[j,k)内部为相等元素
}
cout<<cnt;
return 0;
}
最短连续区间和-----p42(poj 3061)
双指针+贪心
//构造一个窗口
#include<iostream>
using namespace std;
long long n,s,cnt;
int a[4000000];
int main()
{
ios::sync_with_stdio(false);cin.tie();cout.tie();
int t;
cin>>t;
while(t--)
{
cin>>n>>s;
for(int i=1;i<=n;i++)cin>>a[i];
cnt=n+1;
long long l=1,r=1;
long long sum=0;
while(1)
{
while(sum<s&&r<n)sum+=a[r++];//使得r每次多走一个
if(sum<s)break;//核心操作
cnt=min(cnt,r-l);//r实际使窗口外的[l,r)
sum-=a[l++];
}
if(cnt==n+1)cout<<"0\n";
else cout<<cnt<<'\n';
}
return 0;
}