共计 1158 个字符，预计需要花费 3 分钟才能阅读完成。
简单的一道题，想到的有两种方法
方法一：二分查找；由于是两个数和，所以我们从 i = 1 开始枚举，在剩下的 i +1~n 序列中找到 m -a[i] 的数，是一个递增不重复序列的查找问题，之前二分法总结过，所以不再赘述；代码如下：
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=100010;
int coin[maxn];
int n,m;
int binarySearch(int l,int r,int x){
while(l<=r){
int mid=(l+r)/2;
if(coin[mid]==x)
return mid;
else if(coin[mid]>x){
r=mid-1;
}else{
l=mid+1;
}
}
return -1;
}
int main(){
scanf(“%d%d”,&n,&m);
for(int i=1;i<=n;i++){
scanf(“%d”,&coin[i]);
}
int a,b;
int r=-1;
sort(coin+1,coin+n+1);
for(int i=1;i<n;i++){
a=coin[i];
b=m-coin[i];
r=binarySearch(i+1,n+1,b);
if(r!=-1){
break;
}
}
if(r==-1){
printf(“No Solution\n”);
}else{
printf(“%d %d”,a,b);
}
system(“pause”);
return 0;
}
第二种方法：two points；注意的点是避免 i = j 使得重复加同一个值从而导致错误答案；
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=100010;
int coin[maxn];
int n,m;
int main(){
scanf(“%d%d”,&n,&m);
for(int i=1;i<=n;i++){
scanf(“%d”,&coin[i]);
}
int a,b;
int r=-1;
sort(coin+1,coin+n+1);
int i=1,j=n;
int sum;
bool flag=false;
while(i<j){
sum=coin[i]+coin[j];
if(sum==m){
flag=true;
break;
}
else if(sum>m){
j–;
}else{
i++;
}
}
if(!flag){
printf(“No Solution\n”);
}else{
printf(“%d %d”,coin[i],coin[j]);
}
system(“pause”);
return 0;
}
