# Accepted C O(n) Solution with Hash-List table in 3ms.

• Here is my sulotion with hash-list table in C:

``````/**
* Note: The returned array must be malloced, assume caller calls free().
*/
#include <stdlib.h>
#include <stdint.h>

typedef struct hash_node {
struct hash_node *next;
int index;
int value;
} hash_node_t;

typedef struct hash_table {
int size;
hash_node_t **buckets;
} hash_table_t;

hash_table_t *table_new(int size)
{
hash_table_t *table;
int i;
/* find a suitable prime number as table size. */
static int primes[] = { 509, 509, 1021, 2053, 4093, 8191, 16381, 32771, 65521, INT_MAX };
for (i = 1; primes[i] < size; i++)
;
/* alllocate memory for table with buckets at the end of table. */
table = calloc(1, sizeof(hash_table_t) + primes[i-1] * sizeof(hash_node_t *));
table->buckets = (hash_node_t **)(table+1);
table->size = primes[i-1];
return table;
}

void table_free(hash_table_t *table)
{
hash_node_t *node, *save;
int i;
if (table) {
/* loop for all buckets and nodes */
for (i = 0; i < table->size; i++) {
for (node = table->buckets[i]; node != NULL; node = save) {
save = node->next;
free(node);
}
}
free(table);
}
}

hash_node_t *table_put(hash_table_t *table, int index, int value)
{
int hash = abs(value) % table->size;
hash_node_t *node = malloc(sizeof(hash_node_t));
node->index = index;
node->value = value;
node->next = table->buckets[hash];
table->buckets[hash] = node;
return node;
}

hash_node_t *table_get(hash_table_t *table, int value)
{
hash_node_t *node;
int hash = abs(value) % table->size;
if (table) {
/* loop to find out node */
for (node = table->buckets[hash]; node != NULL; node = node->next)
if (node->value == value)
return node;
return NULL;
}
return NULL;
}

int* twoSum(int* nums, int numsSize, int target) {
int key;
int i;
hash_table_t *table;
hash_node_t *node;
int *index = NULL;

table = table_new(numsSize);
for (i = 0; i < numsSize; i++) {
key = target - nums[i];
if (node = table_get(table, key)) {
index = malloc(sizeof(int)*2);
if (i < node->index) {
index[0] = i;
index[1] = node->index;
}
else {
index[0] = node->index;
index[1] = i;
}
break;
}
table_put(table, i, nums[i]);
}
table_free(table);
return index;
}
``````

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