题目要求:
给一个长度为N的整型数组A[1...N]，查找出数组中所有两两之和等于X的整数对时间复杂度不超过O(nlog2n)
做题思路:
先将数组从小到大排序，可用快速排序，然后分别从数组的最左边i=0和最右边j=n-1开始遍历查找：如果A[i] + A[j] < X,i++;如果A[i] + A[j] > X,j--;否则输出A[i] 和A[j]，然后i++,j--;直到i > j停止。
时间复杂度为O(nlog2n),空间复杂度O(1)
#include "stdio.h"
#define ElemType int
int Partition(ElemType A[], int low, int high) { //划分子表
int i;
ElemType pivot = A[low];
while(low < high) {
while (low < high && A[high] >= pivot) --high;
A[low] = A[high];
while (low < high && A[low] <= pivot) ++low;
A[high] = A[low];
}
A[low] = pivot;
return low;
}
void QuickSort(ElemType A[], int low, int high) { //快速排序
if(low < high) {
int pivotpos = Partition(A, low, high);
QuickSort(A, low, pivotpos-1);
QuickSort(A, pivotpos+1, high);
}
}
void findCouple(ElemType A[], int n, ElemType x) { //通过移动i,j查找A[i] + A[j] == X
int k, i = 0, j = n-1;
while (i < j) {
while (i < j && A[i] + A[j] < x) i++;
while (i < j && A[i] + A[j] > x) j--;
if(A[i] + A[j] == x) {
printf("%d %d\n",A[i], A[j]);
i++;
j--;
}
}
}
int main () {
ElemType x = 8;
ElemType A[] = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
int n = sizeof(A)/sizeof(A[0]);
QuickSort(A, 0, sizeof(A)/sizeof(A[0])-1);
findCouple(A, n, x);
}
经过百度，还可以用哈希表来存储数组中的元素,这样我们取得一个数后，可直接判断sum - val 在不在数组中，如果在数组中，则找到了一对二元组，它们的和为sum，该算法的缺点就是需要用到一个哈希表，增加了空间复杂度。
时间复杂度为O(n),空间复杂度为O(n)
