算法1
(朴素做法) 会超时 n^2
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n,m,a[N];
int main()
{
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
int x,y;
for(int i=0;i<n;i++)
{
x=a[i];
for(int j=i+1;j<n;j++)
{
if(a[i]+a[j]==m)
{
cout<<a[i]<<" "<<a[j];
return 0;
}
}
}
puts("No Solution");
return 0;
}
算法2
(双指针) 优化朴素做法双指针 排序 O(nlogn),双指针O(n),总时间复杂度 O(nlogn)。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e5+5;
int n,m,a[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);
for(int i=0,j=n-1;i<j;i++)
{
while(i<j&&a[i]+a[j]>m) j--;//用while而非if
if(i<j&&a[i]+a[j]==m)
{
cout<<a[i]<<" "<<a[j];
return 0;
}
}
puts("No Solution");
return 0;
}
算法三 哈希表 一次循环,所以为 O(n) 。空间复杂度:开辟了一个堆,所以为 O(n)。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_set>
using namespace std;
const int INF = 1e4;
int main()
{
int n,m;
cin>>n>>m;
unordered_set<int> hash;
int v1=INF,v2;
for(int i=0;i<n;i++)
{
int a,b;
cin>>a;
b=m-a;
if(hash.count(b))
{
hash.insert(a);
if(a>b)swap(a,b);
if(a<v1) v1=a,v2=b;
}
else hash.insert(a);
}
if(v1==INF) puts("No Solution");
else cout<<v1<<" "<<v2;
return 0;
}