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


  • 0
    R

    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;
    }


Log in to reply
 

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