題目要求:
給一個(gè)長(zhǎng)度為N的整型數(shù)組A[1...N]祈搜，查找出數(shù)組中所有兩兩之和等于X的整數(shù)對(duì)時(shí)間復(fù)雜度不超過(guò)O(nlog2n)
做題思路:
先將數(shù)組從小到大排序，可用快速排序眨八，然后分別從數(shù)組的最左邊i=0和最右邊j=n-1開(kāi)始遍歷查找：如果A[i] + A[j] < X,i++;如果A[i] + A[j] > X,j--;否則輸出A[i] 和A[j]钞它，然后i++,j--;直到i > j停止。
時(shí)間復(fù)雜度為O(nlog2n),空間復(fù)雜度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) { //通過(guò)移動(dòng)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);
}
經(jīng)過(guò)百度彭沼，還可以用哈希表來(lái)存儲(chǔ)數(shù)組中的元素,這樣我們?nèi)〉靡粋€(gè)數(shù)后，可直接判斷sum - val 在不在數(shù)組中备埃，如果在數(shù)組中姓惑，則找到了一對(duì)二元組褐奴，它們的和為sum，該算法的缺點(diǎn)就是需要用到一個(gè)哈希表于毙，增加了空間復(fù)雜度敦冬。
時(shí)間復(fù)雜度為O(n),空間復(fù)雜度為O(n)
