寻找和为定值的两个数

比眉伴天荒 2022-08-06 00:23 144阅读 0赞

**寻找和为定值的两个数**

# 1. 题目描述 #

给定一个数组（无序或者有序，两种情况都要考虑），找出和为M的两个数。最多时间复杂度能有多少？

https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.02.md

# 2. 数组有序——两端指针扫描法 #

数组有序的情况，在时间复杂度上我们就省去了排序的O(NlogN)。

我们使用两端指针扫描法是比较简单的，时间复杂度为O(N), 空间复杂度为O(1)。如下图所示：

![Center][]

首先我们在数组两端分别放上一个标志：head, tail。

然后，判断它们指向的值之和sum是否等于M，

如果sum==M,  记录结果！head, tail同时往中间移动一次；

如果sum<M, tail往中间移动一次；

如果sum>M, head往中间移动。

直到，head>tail，返回结果~

总共的时间复杂度就是很厉害的O(N), 空间复杂度也只是O(1)。但是注意前提是数组要有序~

程序如下：

#include<iostream>
    using namespace std; 
    
    void FindTwo(int *a, int M, int num)
    {
    	int head=0, tail=num-1; 
    
    	while(head<tail)
    	{
    		int sum=a[head]+a[tail]; 
    		if(sum==M)
    		{
    			cout<<a[head]<<'\t'<<a[tail]<<endl; 
    			head++; 
    			tail--; 
    			continue;
    		}
    
    		if(sum>M)
    		{
    			tail--; 
    			continue; 
    		}
    
    		if(sum<M)
    		{
    			head++; 
    			continue; 
    		}
    	}
    }
    
    int main()
    {
    	int a[10]={2,3,6,8,9,11,14}; 
    	//int a[10]={2,3,6,8,9,11,14};
    	int M=15; 
    	int num=7; 
    
    	FindTwo(a, M, num); 
    
    	return 0; 
    }

# 3. 数组无序——映射hash表或者数组 #

当数组无序的时候，当时我们可以先排序, 然后再使用上面的方法。这是时间复杂度为O(NlogN)，空间复杂度为O(1)。

或者我们还可以使用映射hash表或者数组，详细来说：

把数组M - a\[i\]映射到一个hash表或者是一个数组，然后我们就判断原数组和数组M - a\[i\]时候有元素相等，如果则返回结果。判断相等的方法我们也可以使用两端夹逼方法。

![Center 1][]

这种方法的时间复杂度为O(N), 空间复杂度为O(N)。

ps：其实在无序的情况，还是映射到hash表比较好，映射到数组也不是很好操作~

[Center]: /images/20220806/89a2d24ac3464884b68c8c20e8f291bf.png
[Center 1]: /images/20220806/7639c63ad58c4485aa7f194db409d4c5.png