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


  • 0
    I

    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;
        /* add node to the list head */
        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;
    }
    

Log in to reply
 

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