C solution (6ms) using 'uthash'


  • 0

    Use uthash as your C hash table implementation and save time by focussing on the problem itself.

    typedef struct {
        int key, index;
        UT_hash_handle hh;
    } HashElement;
    
    int* twoSum(int* nums, int numsSize, int target) {
        HashElement *hash = NULL, *elem, *tmp;
        // Allocate and zero out the result array
        int *result = malloc(sizeof(int) * 2); 
        memset(result, 0, sizeof(int) * 2);
    
        if (!numsSize || !nums) { return result; }
        for (int i = 0; i < numsSize; i++) {
            int lookupKey = target - nums[i];
            HASH_FIND_INT(hash, &lookupKey, elem);
            if (elem) {
                result[0] = elem->index;
                result[1] = i;
                return result;
            }
            elem = malloc(sizeof(HashElement));
            elem->key = nums[i];
            elem->index = i;
            HASH_ADD_INT(hash, key, elem);
        }
        
        // Free up every element in the hash table. 
        HASH_ITER(hh, hash, elem, tmp) { free(elem); }
        return result;
    }
    

    The following solution has the same logic but uses an integer array based hash table.

    #define hash_new(h, max)        int h##Pos[max]; int h##Neg[max]; \
                                    for (int i = 0; i < max; i++) { h##Pos[i] = -1; h##Neg[i] = -1; }
    #define hash_get(h, key)        ((key) < 0? h##Neg[key]: h##Pos[key])
    #define hash_set(h, key, val)   if ((key) < 0) h##Neg[key] = val; else h##Pos[key] = val
    #define hash_exist(h, key)      (hash_get(h, key) != -1)
    
    int* twoSum(int* nums, int numsSize, int target) {
        if (!nums || numsSize <= 0) return NULL;
        hash_new(map, 100000);
        
        for (int i = 0; i < numsSize; i++) {
            if (hash_exist(map, target - nums[i])) {
                int *result = malloc(sizeof(int) * 2);
                result[0] = hash_get(map, target - nums[i]);
                result[1] = i;
                return result;
            }
            hash_set(map, nums[i], i); 
        }
        return NULL;
    }
    

Log in to reply
 

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