算法
双指针
思路
1.现将数组从小到大(从大到小也没什么问题)排序(双指针多数都应该先排序,并且题目要求输出v1最小的一组答案)
2.条件(左指针比右指针要小)
(1)左指针+右指针的数>m,则需要其中的一个数变小,由于排好序后,左边的要比右边的小,所以,应当让右指针左移;
(2)反之,左指针右移
3.若经过以上的步骤后,仍然没有得出结果,则输出No Solution
C++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll N=1e5+1e4;
ll n,m;
ll a[N];
ll tou,wei;//左指针(tou),右指针(wei)
bool flag=false;
signed main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(ll i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);//排序
tou=1,wei=n;
while(tou<wei)//条件(左指针比右指针要小)
{
if(a[tou]+a[wei]==m)//满足题目条件,输出
{
cout<<a[tou]<<" "<<a[wei];
flag=true;
return 0;
}
if(a[tou]+a[wei]>m)wei--;//左指针+右指针的数>m,则需要其中的一个数变小,由于排好序后,左边的要比右边的小,所以,应当让右指针左移
else tou++;//反之,左指针右移
}
if(flag==false)cout<<"No Solution";
return 0;
}