算法练习：两数之和

题目：给定一个整型数组，是否能找出两个数使其和为指定的某个值？注：整型数组中不存在相同的数。

一、解题方法

1、暴力破解法(时间复杂度O(n^2) )

这是最容易想到的一种方法，即使用两层循环，从数组里取出一个数，然后在此数之后部分找出另外一个数，计算两数之和，判断是否等于指定值。如下：

//直观的办法，使用两个循环
bool IsExistSumOfTwoNum( int nArray[], int nCount, int nSum )
{
	bool bRet = false;
	for ( int i = 0; i < nCount - 1; ++i )
	{
		for ( int j = i + 1; j < nCount; ++j )
		{
			if ( ( nArray[i] + nArray[j] ) == nSum )
			{
				bRet = true;
				break;
			}
		}
	}
	
	return bRet;	
}

此种方法的的时间复杂度为O(n^2)，那么能否降低此复杂度呢？答案是可以的，请看第二种方法。

2、排序加首尾指针（时间复杂度O(nlogn) ）

先对数组进行从小到大的排序，然后设置首尾指针，从首尾两端开始移动，一次移动一端的指针，直至两指针相遇或者两指针指向的数的和为指定的值。

假设两指针为i，j，其中i < j，如果a[i]、a[j]之和大于指定值，那么要找的两个数一定在j的左侧，如果a[i]、a[j]之和小于指定值，那么要找的两个数一定在i的右侧。可用反证法证明此结论的正确性，证明略。

bool IsExistSumOfTwoNum( int nArray[], int nCount, int nSum )
{
	//从小到大排序
	std::sort( nArray, nArray+nCount, std::less<int>() );

	//首尾指示
	int i = 0; 
	int j = nCount - 1;

	bool bRet = false;
	while( i < j )
	{
		if ( ( nArray[i] + nArray[j] ) == nSum )
		{
			bRet = true;
			break;
		}
		else if ( ( nArray[i] + nArray[j] ) > nSum  )
		{
			--j;
		}
		else
		{
			++i;
		}
	}

	return bRet;	
}

此种算法中，一开始有一个排序，最好的排序的时间复杂度可为O(nlogn)，比如堆排序、归并排序、快速排序。While循环至多扫描一遍数组，所以其时间表复杂度为O(n)。由此可得，最终的时间复杂度为O(nlogn)。那么能否再降低时间复杂度呢？答案还是可以的，但是这时需要一个额外的存储空间，请看第三种方法。

3、利用哈希表（时间复杂度O(n) ）

将复杂度为O(nlogn)降低至O(n)，首先想到的是哈希表，因为哈希表的查找时间复杂度为O(n)。

扫描一遍数组，将其数组各个值保存至哈希表中，比如键值：<数组值--索引>。然后再次开始从头扫描数组，检查指定值与当前值的差值是否在哈希表中（特殊情况：如果遇到差值为当前值时，那么不应返回，因为数组中的值是不相同的）。

程序代码实现说明：程序中使用c++标准库中的set代替哈希表，因为标准库中还未收录哈希表相关部分。此处若需要两数的索引信息，可以考虑使用map。因为set、map内部使用的是红黑树数据结构，查找效率高，具体的复杂度，我还没好好研究，呵呵。希望此处用set代替哈希表，不要引起误会，姑且将它理解为查找复杂度为常数时间的东西吧。

//使用额外的存储空间
bool IsExistSumOfTwoNum( int nArray[], int nCount, int nSum )
{
	//打描一遍数组，将值存放于哈希表中
	//（注：此处使用set代替下哈希表，它内部实现说是红黑树，还没仔细研究过，呵）
	std::set<int> siSetTemp;
	int i = 0;
	bool bRet = false;
	for ( i = 0; i < nCount; ++i )
	{
		siSetTemp.insert( nArray[i] );
	}

	for ( i = 0; i < nCount; ++i )
	{
		std::set<int>::iterator it = siSetTemp.find( nSum - nArray[i] );
		if ( it != siSetTemp.end() && (nSum != 2 * nArray[i] ) )
		{
			bRet = true;
			break;
		}
	}

	return bRet;
 		
}

此种算法中，哈希表的查找是常数时间，所以时间复杂度为O（n），空间复杂度为

O（n），即数组大小O（n）。

二、扩展问题

如果要返回其中所有的可能或者数组里面存在相同的数，那么应当怎么解决呢？相信有了以上的知识，这个解决起来也不难。一个是开辟一个保存结果的数组，搜索完整个数组空间；另外一个无非就是让哈希表中多存放点数据。

系列文章说明:
1.本系列文章[算法练习],仅仅是本人学习过程的一个记录以及自我激励,没有什么说教的意思。如果能给读者带来些许知识及感悟，那是我的荣幸。
2.本系列文章是本人学习陈东锋老师《进军硅谷，程序员面试揭秘》一书而写的一些心得体会，文章大多数观点均来自此书，特此说明！
3.文章之中,难免有诸多的错误与不足,欢迎读者批评指正,谢谢.

作者：山丘儿
转载请标明出处，谢谢。原文地址：http://blog.csdn.net/s634772208/article/details/46388789