先排序(nlogn),然后从两头往中间逼近(n)
正确性证明如下:
对于排序后的数列 a1, a2, a3… an-1, an;
若存在解 …ai, …, aj…
必然有lo或hi其中一个先到达ai或aj
lo(hi)不可能到达aj(ai)
若lo先到达ai, 此后的循环中, alo + ahi >= m恒成立,
则持续进行hi–,直到hi到达aj,跳出循环
#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[100005];
int main(void){
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++)
scanf("%d", arr+i);
sort(arr, arr+n);
int lo = 0, hi = n-1;
while(lo < hi && arr[lo] + arr[hi] != m){
while(lo < hi && arr[lo] + arr[hi] > m)
hi--;
while(lo < hi && arr[lo] + arr[hi] < m)
lo++;
}
if(lo < hi && arr[lo] + arr[hi] == m)
printf("%d %d", arr[lo], arr[hi]);
else
printf("No Solution");
}
最原始的思路,我感觉还是得做一些优化了,毕竟java的话 就TLE了