217.c

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

structHashNode {
intdata;
structHashNode*next;
};

staticinlineinthash(intnum, intsize) {
intindex=num % size;
return (index>0) ? (index) : (-index);
}

boolcontainsDuplicate(int*nums, intnumsSize) {
if (numsSize<2) return false;
boolduplicated= false;

inthash_size=numsSize / 2+1; /* proper size can be faster */
structHashNode**hash_table
= (structHashNode**)calloc(hash_size, sizeof(structHashNode*));

inti;
for (i=0; i<numsSize; i++) {
intindex=hash(nums[i], hash_size);
structHashNode**p=hash_table+index;

while (*p) {
if ((*p)->data==nums[i]) {
duplicated= true;
 goto OUT;
 }
p=&((*p)->next);
 }

structHashNode*new_node
= (structHashNode*)malloc(sizeof(structHashNode));
new_node->data=nums[i];
new_node->next=NULL;

*p=new_node;
 }

OUT:
for (i=0; i<hash_size; i++) {
structHashNode*t=hash_table[i];
structHashNode*x=NULL;
while (t) {
x=t->next;
free(t);
t=x;
 }
 }
free(hash_table);

returnduplicated;
}

intmain() {
intnums[] = { 1, 3, 5, 7, 9, 7 };
/* should be 1 */
printf("%d\n", containsDuplicate(nums, sizeof(nums) / sizeof(nums[0])));

return0;
}