预备思考:要求输出值,那么可以对数组排序,这样我们更好操作,也从某种意义上降低了时间复杂度

1.朴素的想法

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+9;
ll a[N],sum=0,m;

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	int n;cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i];
	cin>>m;
	sort(a+1,a+1+n);
	for(int i=1;i<=n-1;++i)
	{
		for(int j=n;j>=i+1;--j)
		{
			if(a[i]+a[j]==m)
			{
				cout<<a[i]<<' '<<a[j];
				return 0;
			}
		}
	}
	cout<<"No";
	return 0;
}

2.双指针

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+9;
ll a[N],m;

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	int n;cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i];
	cin>>m;
	sort(a+1,a+1+n);
	int i=1,j=n;
	while(i!=j)
	{
		if(a[i]+a[j]==m)
		{
			cout<<a[i]<<' '<<a[j];
			return 0;
		}
		else if(a[i]+a[j]<m)
		{
			i++;
		}
		else
		{
			j--;
		}
	}
	cout<<"No";
	return 0;
}

给个错解思考其中问题(超时版本)

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+9;
ll a[N],sum=0,m;

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	bool find=false;
	int n;cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i];
	cin>>m;
	int min_val=0x3f3f3f3f;
	int ans;
	for(int i=1;i<=n-1;++i)
	{
		for(int j=i+1;j<=n;++j)
		{
			if(a[i]+a[j]==m)
			{
				if(min(a[i],a[j])<min_val)
				{
					find=true;
					min_val=min(a[i],a[j]);
					ans=max(a[i],a[j]);
				}
			}
		}
	}
	if(!find)cout<<"No";
	else cout<<min_val<<' '<<ans;
}