算法练习题：两数之和
题目：给定一个整型数组，是否能找出两个数使其和为指定的某个值？注：整型数组中不存在相同的数。
一、解题方法
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