Accepted C solution of HashTable only in 4ms


  • 0
    R

    This program runs in 4ms. And I think hashtable in my program could be optimized further.

    #define INVALID 2147483647
    
    typedef struct {
        int value;
        int index;
        int valid;
    } Hash;
    
    int *twoSum(int numbers[], int n, int target) {
        int i = 0;
        int index = 0;
        int size = abs(numbers[0]);
        int *answer = (int*)malloc(2*sizeof(int));
        for (i = 1; i < n; i++) {
            if (abs(numbers[i]) > size) size += abs(numbers[i]);
        }
        Hash *hash = (Hash*)malloc(size*sizeof(Hash));
        for (i = 0; i < size; i++) {
            hash[i].value = INVALID;
            hash[i].index = -1;
            hash[i].valid = 0;
        }
        for (i = 0; i < n; i++) {
            index = abs(numbers[i]);
            if (hash[index].valid == 0) {
                hash[index].value = target - numbers[i];
                hash[index].index = i+1;
                hash[index].valid = 1;
            } else if (((hash[index].value == numbers[i] && (target == 0 || hash[index].value + numbers[i] == target)))
                      && hash[index].valid == 1) {
                answer[0] = hash[index].index;
                answer[1] = i+1;
                free(hash);
                return answer;
            }
        }
        for (i = 0; i < size; i++) {
            index = abs(hash[i].value);
            if (index < size && hash[index].valid == 1) {
                if (hash[i].index < hash[index].index) {
                    answer[0] = hash[i].index;
                    answer[1] = hash[index].index;
                } else if (hash[i].index > hash[index].index) {
                    answer[0] = hash[index].index;
                    answer[1] = hash[i].index;
                } else continue;
                free(hash);
                return answer;
            }
        }
    }

Log in to reply
 

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