51nod 1001 数组中和等于K的数对（STL/双指针）

淩亂°似流年 2023-07-13 15:25 21阅读 0赞

给出一个整数K和一个无序数组A，A的元素为N个互不相同的整数，找出数组A中所有和等于K的数对。例如K = 8，数组A：\{-1,6,5,3,4,2,9,0,8\}，所有和等于8的数对包括(-1,9)，(0,8)，(2,6)，(3,5)。

**输入**  
第1行：用空格隔开的2个数，K N，N为A数组的长度。(2 <= N <= 50000，-10^9 <= K <= 10^9)  
第2 - N + 1行：A数组的N个元素。（-10^9 <= A\[i\] <= 10^9)

**输出**  
第1 - M行：每行2个数，要求较小的数在前面，并且这M个数对按照较小的数升序排列。  
如果不存在任何一组解则输出：No Solution

**输入样例**  
8 9  
\-1  
6  
5  
3  
4  
2  
9  
0  
8  
**输出样例**  
\-1 9  
0 8  
2 6  
3 5

**解法一：运用c++的STL函数 lower\_bound(a,a+n,num)-a;**

a数组必须有序  
upper\_bound(a+i,a+j,x)-a //返回第一个大于x的数的位置  
lower\_bound(a+i,a+j,x)-a //返回的是第一个大于等于x的数的位置

注意此函数为前闭后开，  
比如你找从1~n ： lower\_bound(a+1,a+n+1,x)-a ，如果找不到返回 n+1

本题是从前往后找第一个大于等于k-a\[i\]的为位置，找到后在判断是不是和为k

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<map>
    #include<queue>
    #include<vector>
    #include<set>
    #include<sstream>
    using namespace std;
    typedef long long ll;
    const ll maxn=1e6+10;
    const ll inf=0x3f3f3f3f3f3f3f3f;
    ll a[maxn]; 
    int main()
    { 
    	ios::sync_with_stdio(false);
    	cin.tie(0);cout.tie(0);
    	ll k,n;
    	cin>>k>>n;
    	for(int i=0;i<n;i++)
    		cin>>a[i];
    	sort(a,a+n);
    	ll flag=0;
    	for(int i=0;i<n;i++)
    	{ 
    		ll ans=lower_bound(a+i+1,a+n,k-a[i])-a;
    		if(ans!=n&&a[i]+a[ans]==k)
    		{ 
    			cout<<a[i]<<" "<<a[ans]<<'\n';
    			flag=1;
    		}
    	}
    	if(!flag)
    		cout<<"No Solution"<<'\n';
    	return 0;
    }

**解法二：双指针**（指针只能往里走，也就是只能 l++或者r–）  
数组从小到大排序，左指针 l=0，右指针 r=n-1  
if( a\[l\]+a\[r\]==k ) 说明找到了，输出答案，l++，r–  
if( a\[l\]+a\[r\]<k ) 说明找小了 右指针不能变大，所以左指针右移1位，l++  
if( a\[l\]+a\[r\]>k ) 说明找大了 左指针不能变小，所以右指针左移1位，r–

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<map>
    #include<queue>
    #include<vector>
    #include<set>
    #include<sstream>
    using namespace std;
    typedef long long ll;
    const ll maxn=1e6+10;
    const ll inf=0x3f3f3f3f3f3f3f3f;
    ll a[maxn]; 
    int main()
    { 
    	ios::sync_with_stdio(false);
    	cin.tie(0);cout.tie(0);
    	ll k,n;
    	cin>>k>>n;
    	for(int i=0;i<n;i++)
    		cin>>a[i];
    	sort(a,a+n);
    	ll l=0,r=n-1,flag=0;
    	while(l<r)
    	{ 
    		if(a[l]+a[r]==k)
    		{ 
    			cout<<a[l]<<" "<<a[r]<<'\n';
    			l++;
    			r--; 
    			flag=1;
    		}
    		else if(a[l]+a[r]<k)
    			l++;
    		else
    			r--;
    	}
    	if(!flag)
    		cout<<"No Solution"<<'\n';
    	return 0;
    }