11.4 找一对数

客官°小女子只卖身不卖艺 2022-05-14 01:09 86阅读 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)。  
Input  
第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)  
Output  
第1 - M行：每行2个数，要求较小的数在前面，并且这M个数对按照较小的数升序排列。  
如果不存在任何一组解则输出：No Solution。  
Input示例  
8 9  
\-1  
6  
5  
3  
4  
2  
9  
0  
8  
Output示例  
\-1 9  
0 8  
2 6  
3 5

![70][]

> 一般达到1亿次以上，就会超时。

![70 1][]

二分法代码：

#include<iostream>
    #include<algorithm>
    #define MAXN 100010
    using namespace std;
    int a[MAXN];
    
    int BinarySearch(int a[], int n, int k)
    {
    	int left = 0;
    	int right = n - 1;
    	int flag = 0;
    	while(left <= right)
    	{
    		int mid = left + (right - left)/2;
    		if(a[mid] == k)  
    		{
    			flag = 1;
    			break;
    		}
    		else if(a[mid] > k)
    			right = mid - 1;
    		else
    			left = mid + 1;
    	}
    	return flag;
    }
    
    int main()
    {
    	int n,m,flag=0;
    	cin >> m >> n;
    	for(int i = 0; i < n; ++i)
    		cin >> a[i];
    	sort(a,a+n);
    	for(int i = 0; i < n; ++ i)
    	{
    		int k = m - a[i];
    	//	cout << k << endl;
    		if(BinarySearch(a,n,k))
    		{
    			flag = 1;
    			if(a[i] == k && a[i] == a[i+1]) //注意两个数相等，并且和刚好为m的情况，此时只需要输出一组数据即可 
    			{
    				cout << a[i] << " " << k << endl;
    				break;
    			}
    			if(a[i] >= m/2) break;
    			cout << a[i] << " " << k << endl;			
    		}
    		 
    	}
    	if(flag == 0)
    		cout << "No Solution" << endl;
    	return 0;
    }

![70 2][]

> 解法3的速度要更快一些。如果a\[i\]+a\[j\]>m,由于a\[\]是从小到大的有序序列，因此肯定a\[j\]大了，所以需要j往前移动一位。

#include<iostream>
    #include<algorithm>
    #define MAXN 100010
    using namespace std;
    int a[MAXN];
    
    int main()
    {
    	int n,m;
    	cin >> m >> n;
    	for(int i = 0; i < n; ++ i)
    		cin >> a[i];
    	sort(a,a+n);
    	int i = 0;
    	int j = n - 1;
    	int flag = 0;
    	while(i < j)//不能加等号，否则会出现输出m/2的情况
    	{
    		int k = a[i] + a[j];
    		if( k == m)
    		{
    			cout << a[i++] << " " << a[j--] << endl;//相等的时候记得i和j要更新，否则会一直循环 
    			flag = 1;
    		 } 
    		else if( k > m)//说明a[j]太大了 
    			-- j;
    		else 
    			++ i; 
    	}	
    	if(!flag)
    		cout << "No Solution" << endl;
    }

![70 3][]

![70 4][]

[70]: /images/20220514/7b3aa04c0b8146a88bcc709d305f8aac.png
[70 1]: /images/20220514/ff0a130c46cf4cf2bba986c30e932a8c.png
[70 2]: /images/20220514/ce4b74bf05664e2d9f3d5f4f2520f91e.png
[70 3]: /images/20220514/80c6772cea664194831d1988d0278483.png
[70 4]: /images/20220514/fb7433123a4a477290767df7ae4f57f3.png