哈希(5) - 检测数组A[]中是否存在元素对其和为x
给定一个包括n个数值的数组A[]以及另一个数字x，判断数组中是否存在一对元素，它们的和等于x。

方法1 (使用排序)

算法:
hasArrayTwoCandidates (A[], arrSize, sum)
1) 对数组进行递增排序
2) 初始化已排序数组中的两个索引值
    (a) 将最左侧的数组位置0做为第一个索引left = 0
    (b) 将最右侧的数组位置做为第二个索引right = arrSize-1
3) Loop while left < right.
    (a) if (A[left] + A[right] == sum) then return 1
    (b) else if( A[left] + A[right] < sum ) then left++
    (c) else right--
4) 数组中没有找到匹配的成对元素 - return 0

时间复杂度：取决于我们所使用的排序算法。如果使用归并排序或堆排序，则最坏情况是nlogn。如果使用快速排序，则最坏情况为O(n^2)。
辅助空间： 也取决于排序算法。例如，归并排序使用的辅助空间为O(n)，而堆排序是O(1)。

例如:
存在一个数组A = {1, 4, 45, 6, 10, -8}，并且需要查找的sum为16。

首先对数组排序：
A = {-8, 1, 4, 6, 10, 45}

初始化这两个索引：left = 0, right = 5
A[left] + A[right] ( -8 + 45) > 16 => right索引递减. 现在right变成了10
A[left] + A[right] ( -8 + 10) < 16 => left索引递增. 现在left变成了1
A[left] + A[right] ( 1 + 10) < 16 => left索引递增. 现在left变成了4
A[left] + A[right] ( 4 + 10) < 14 => left索引递增. 现在left变成了6
A[left] + A[right] ( 6 + 10) == 16 => 找到了匹配的元素对(return 1)

注意: 如果存在多对元素的和等于sum，此算法只报告首次发现的这对元素。

代码实现:

#include <iostream>

void quickSort(int *, int , int );

bool hasArrayTwoCandidates(int A [], int arrSize , int sum )
{
        int l, r;

        //对数组元素进行排序
       quickSort( A, 0, arrSize - 1);

        //在已排序数组中查找这两个元素
       l = 0;
       r = arrSize - 1;
        while (l < r)
       {
               if ( A[l] + A[r] == sum)
                      return 1;
               else if ( A[l] + A[r] < sum)
                     l++;
               else // A[i] + A[j] > sum
                     r--;
       }
        return 0;
}

int main()
{
        int A[] = { 1, 4, 45, 6, 10, -8 };
        int sum = 16;
        int arrSize = 6;

        if (hasArrayTwoCandidates(A, arrSize, sum))
              std::cout << "Array has two elements with sum 16\n" ;
        else
              std::cout << "Array doesn't have two elements with sum 16\n" ;

        return 0;
}

//下面的代码用于实现快速排序。
void exchange(int *a , int *b )
{
        int temp = * a;
       * a = * b;
       * b = temp;
}

//数组最后元素做为mid元素，进行排序
int partition(int A [], int si , int ei )
{
        int x = A[ ei];
        int i = ( si - 1);

        for ( int j = si; j <= ei - 1; j++)
       {
               if ( A[j] <= x)
              {
                     i++;
                     exchange(& A[i], & A[j]);
              }
       }
       exchange(& A[i + 1], & A[ ei]);
        return (i + 1);
}

/* 快速排序的实现
A[] --> Array to be sorted
si  --> Starting index
ei  --> Ending index
*/
void quickSort(int A [], int si , int ei )
{
        int pi;    //Partitioning index
        if ( si < ei)
       {
              pi = partition( A, si, ei);
              quickSort( A, si, pi - 1);
              quickSort( A, pi + 1, ei);
       }
}

方法2 (使用哈希表)

如果数值范围已知的话，则此方法为O(n)时间。
假设给定的数组为A[]，和为sum。

1) 初始化哈希表M[] = {0, 0, …}
2) 遍历数组，每个元素进行下面的操作：
(a) 如果M[sum - A[i]]设置为了true, 则存在匹配的一对元素(A[i], sum – A[i])
(b) 将元素M[A[i]]置为true

代码实现:

#include <iostream>

#define MAX 10000

void findPairs(int arr[], int arrSize, int sum)
{
	//定义并初始这个map
	bool binMap[MAX];
	memset(binMap, 0, sizeof(binMap) / sizeof(bool));

	for (int i = 0; i < arrSize; i++)
	{
		int temp = sum - arr[i];
		if (temp >= 0 && binMap[temp])
		{
			std::cout << "Pair with given sum " << sum << " is (" << arr[i] << ", " << temp << ")\n";
		}
		binMap[arr[i]] = true;
	}
}

int main()
{
	int A[] = { 1, 4, 45, 6, 10, 8 };
	int n = 53;
	int arr_size = sizeof(A) / sizeof(int);
	findPairs(A, arr_size, n);
	return 0;
}

输出：
Pair with given sum 53 is (8, 45)

时间复杂度: O(n)
辅助空间: O(R)，其中R是数组中元素整数的范围。

如果数组中包含负数，这个方法也可以正常运行。唯一对负数需要做的事情就是将所有数转换为正数，利用将最小负整数的绝对值加上其它数字。