题解
解法一:排序 + unordered_map
也可以不排序,不过后面需要遍历完才能确定最小值, unordered_map
底层是用哈希表实现的,
也可以用数组代替,但会增加很多不必要的空间浪费。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int arr[N];
int main() {
int n, m;
unordered_map<int, int> mmp;
cin >> n >> m;
for(int i = 0; i < n; i++) {
cin >> arr[i];
mmp[arr[i]]++;
}
sort(arr, arr + n);
for(int i = 0; i < n; i++) {
if(mmp[m - arr[i]]) {
if(arr[i] * 2 == m && mmp[m - arr[i]] == 1) continue;
cout << min(arr[i], m - arr[i]) << " " << max(arr[i], m - arr[i]) << endl;
return 0;
}
}
cout << "No Solution" << endl;
return 0;
}
解法二: 排序 + lower_bound
排完序以后,使用二分查找,lower_bound
会找到第一个大于等于key
的数的下标,判断一下是否等于m - arr[i]
即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int arr[N];
int main() {
int n, m;
cin >> n >> m;
for(int i = 0; i < n; i++) cin >> arr[i];
sort(arr, arr + n);
for(int i = 0; i < n; i++) {
int pos = lower_bound(arr, arr + n, m - arr[i]) - arr;
if(pos != i && arr[pos] == m - arr[i]) {
cout << arr[i] << " " << arr[pos] << endl;
return 0;
}
}
cout << "No Solution" << endl;
return 0;
}
解法三:排序 + 双指针
分成三种情况:
arr[l] + arr[r] > m ,则左移r指针
arr[l] + arr[r] < m ,则右移l指针
arr[l] + arr[r] == m,则直接输出即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int arr[N];
int main() {
int n, m;
cin >> n >> m;
for(int i = 0; i < n; i++) cin >> arr[i];
sort(arr, arr + n);
int l = 0, r = n - 1;
while(l < r) {
if(arr[l] + arr[r] > m) r--;
else if(arr[l] + arr[r] < m) l++;
else {
cout << arr[l] << " " << arr[r] << endl;
return 0;
}
}
cout << "No Solution" << endl;
return 0;
}