- 这是道很妙的题目(不就是哈希吗),但是其实这题没必要,M比较小,双指针即可:
- 问题简单来说就是找 a + b = m
- 将原数组排序得到有序数组我们想得到该解最简单就是暴力
下面是最暴力的做法(可能不能AC)
for(int i = 1; i <= n; i++){
for(int j = i+1; j <=n ;j++){
if(a[i] + a[j] == m ){
cout<<a[i]<<' '<<a[j]<<endl;
return 0;//求最小解,后面的解就不要了
}
}
}
我们可以这么想:一串有序(递增,包括相等)的数组要求两个数相加等于另外一个数
那我们干脆取第一个数和最后一个数为开始位置(省事啊),则有:
- 如果这两个数相加比 m (要求的数)大,则我们要让这两个数之和减小
- 反之我们要让这两个数之和增大
- 已经知道这数组是递增的那我要这两个数之和更大,那不就是取 原来取的后面那个数字 的前面一个数,反之亦然
这里可以用两个指针分别表示取左边和右边的数字
#include<bits/stdc++.h>
#define MAXN 100005
using namespace std;
int n,m,a[MAXN];
int main(){
cin>>n>>m;
for(int i = 1; i <= n; i++) scanf("%d",a+i);
sort(a+1,a+1+n);
for(int i = 1,j = n; i < j; ){
if(a[i] + a[j] > m){
j--;//比要求的数大 那就取较小的数
}
else if(a[i] + a[j] < m) {
i++;//比要求的数小 那就取较大的数
}
else{
cout<<a[i]<<' '<<a[j]<<endl;
return 0;
}
}
cout<<"No Solution"<<endl;
return 0;
}
可能比较拗口(语文不行),向各位大佬膜拜 Orz 新年快乐!!!