# Hand-built Hash Table O(n) Solution in C (4ms)

• typedef struct HashEntry {
int idx;
int value;
struct HashEntry* next;
} HashEntry;

typedef struct HashTable {
int length;
HashEntry **entryList;
} HashTable;

int* twoSum(int* nums, int numsSize, int target) {
HashTable table;
int i, table_idx, goal;
HashEntry* p;
int* res = (int*)malloc(2sizeof(int));
res[0] = -1; res[1] = -1;
table.length = 769; // a rather reasonable prime number good for hashing
table.entryList = (HashEntry
*)malloc(table.lengthsizeof(HashEntry));
for (int i = 0; i < table.length; i++) {
table.entryList[i] = NULL;
}
for (i = 0; i < numsSize; i++) {
table_idx = abs(nums[i] % table.length);
HashEntry* entry = (HashEntry*)malloc(sizeof(HashEntry));
entry->idx = i;
entry->value = nums[i];
entry->next = NULL;
p = table.entryList[table_idx];
if (p == NULL) {
table.entryList[table_idx] = entry;
continue;
}
while (p->next != NULL)
p = p->next;
p->next = entry;
}
for (i = 0; i < numsSize; i++) {
goal = target - nums[i];
table_idx = abs(goal % table.length);
p = table.entryList[table_idx];
while (NULL != p) {
if (p->value == goal && p->idx != i) {
res[0] = i;
res[1] = p->idx;
return res;
}
p = p->next;
}
}
return res;
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.