双指针-two pointers的应用
1.枚举输出解法:
#include <iostream>
using namespace std;
int num[1000];
int main(){int result,n;cin>>result>>n;for(int i=0;i<n;i++)cin>>num[i];for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)if(num[i]+num[j]==result)cout<<num[i]<<","<<num[j]<<endl;return 0;
}
2.分别从头尾两个位置开始:
#include <iostream>
using namespace std;
int num[1000];
int main(){int result,n,x=0,y=0;cin>>result>>n;y=n-1;//末端for(int i=0;i<n;i++)cin>>num[i];if(x<n&&y<n)while(x<y){//分别从头尾开始比较if(num[x]+num[y]==result){//符合输出cout<<num[x]<<","<<num[y]<<endl;x++;y--;}else if(num[x]+num[y]<result)//比目标数小,x往右端,大数移动x++;else y--;//比目标数大,y往左端,小数移动}return 0;
}
由小到大合并两个递增序列
#include <iostream>
using namespace std;
int a[100],b[100],c[100];
int merge(int a[],int b[],int c[],int n,int m){int i=0,j=0,index=0;while(i<n&&j<m){//要不断比较装入:while循环if(a[i]<=b[j])c[index++]=a[i++];else c[index++]=b[j++];}while(i<n&&j>=m) c[index++]=a[i++];//当b序列已经遍历结束while(i>=n&&j<m) c[index++]=b[j++];//当a序列已经遍历结束return index;
}
int main(){int n,m,y=0;cin>>n>>m;for(int i=0;i<n;i++)cin>>a[i];for(int j=0;j<m;j++)cin>>b[j];y=merge(a,b,c,n,m);for(int j=0;j<y;j++){//避免多余的逗号if(j!=y-1)cout<<c[j]<<",";else cout<<c[j]<<endl;}return 0;
}
小结:通过下标进行充分比较判断处理