C++的寻找数组问题

来源：百度知道 编辑：UC知道 时间：2024/05/18 00:40:34
数组A，有n个数，每个数都小于X。

找出所有的组（Ai，Aj）
让两数之和为X+1；

要求，时间复杂度为n。

#include <string.h>

#define X 30
#define N 5

int main()
{
int A[N] = {15, 3, 4, 16, 27};
int H[X];
int i;

memset(H, 0, sizeof(int) * X); /*这里不知道算不算复杂度杂度在O(n)内？*/

for (i = 0; i < N; i++) {
if (H[X+1-A[i]] != 0) {
printf ("A[%d] = %d, A[%d] = %d\n", H[X+1-A[i]]-1, X+1-A[i], i, A[i] );
}
H[A[i]] = i+1;
}

return 0;
}

这里假设数组的所有元素不相同，
如果使用开地址法存这个hash表的话，元素相同也没关系了。

自己想去吧

妙解，O(n)+O(n)=O(n)