检测数组A[]中是否存在元素对其和为x

给定一个包括n个数值的数组A[]以及另一个数字x，判断数组中是否存在一对元素，它们的和等于x。方法1 (使用排序)算法:hasArrayTwoCandidates (A[], arrSize, sum)1) 对数组进行递增排序2) 初始化已排序数组中的两个索引值 (a) 将最左侧的数组位置0做为第一个索引left = 0 (b) 将最右侧的数组位置做为第二个索引right = arrSize-13) 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 = 5A[left] + A[right] ( -8 + 45) > 16 => right索引递减. 现在right变成了10A[left] + A[right] ( -8 + 10) < 16 => left索引递增. 现在left变成了1A[left] + A[right] ( 1 + 10) < 16 => left索引递增. 现在left变成了4A[left] + A[right] ( 4 + 10) < 14 => left索引递增. 现在left变成了6A[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] > sumr–;}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" ;elsestd::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 sortedsi –> Starting indexei –> Ending index*/void quickSort(int A [], int si , int ei ){int pi; //Partitioning indexif ( 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 10000void findPairs(int arr[], int arrSize, int sum){//定义并初始这个mapbool 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是数组中元素整数的范围。如果数组中包含负数，这个方法也可以正常运行。唯一对负数需要做的事情就是将所有数转换为正数，利用将最小负整数的绝对值加上其它数字。

我想，这就是旅行的真义吧。