Confused with my C solution.


  • 0
    I

    Here's my C solution. It goes well in my local environment(I feel it's a little difficult to debug online so I try to debug it locally). But the result of online check shows "Runtime error". I can't figure out why. Is that because my algorithm is too bad?
    Here's the result on my mac:

    i4never-MacBook-Pro:leetcode FC$ ./a.out 
    index1 = 0 index2 = 2 
    

    Here's the code:

    #include <stdio.h>
    #include <stdlib.h>
    
    /**
     * Note: The returned array must be malloced, assume caller calls free().
     */
     
    const int P = 109;
     
    struct HashNode{
        int index;
        struct HashNode * next;
    };
    
    void show_HashTable(struct HashNode * HT)
    {
        for (int i = 0 ; i < P ; i++)
        {
            printf("%d ",HT[i].index);
        }
    }
    
    struct HashNode * init_HashTable(struct HashNode* HT)
    {
        HT = (struct HashNode*)malloc(P*sizeof(struct HashNode));
        for (int i = 0 ; i < P ; i++)
        {
            HT[i].index = -1;
            HT[i].next = NULL;
        }
        return HT;
    }
    
    void free_HashTable(struct HashNode* HT)
    {
        struct HashNode* temp1;
        for (int i = 0 ; i < P ; i++)
        {
            temp1 = HT[i].next;
            while (temp1 != NULL)
            {
                struct HashNode* temp2 = temp1->next;
                free(temp1);
                temp1 = temp2;
            }
        }
        free(HT);
    }
    
    int * twoSum(int* nums, int numsSize, int target) {
        int *result;
        result = (int*) malloc(sizeof(int)*2);
        
        struct HashNode* HT;
        HT = init_HashTable(HT);
        // show_HashTable(HT);
        
        for (int i = 0 ; i < numsSize ; i++)
        {
            // printf("iteration %d\n",i);
            struct HashNode * temp;
            temp = &HT[nums[i]%P];
            while(temp && temp->index != -1)
            {
                if (nums[temp->index] + nums[i] == target)
                {
                    // find the match one
                    result[0] = temp->index;
                    result[1] = i;
                    // show_HashTable(HT);
                    // printf("%d %d", result[0],result[1]);
                    free_HashTable(HT);
                    return result;
                }
                temp = temp->next;
            }
            // no element matchs, add number to HT, key = remains mod P
            int key = (target-nums[i])%P;
            if (HT[key].index == -1)
            {
                //doesn't conflict
                HT[key].index = i;
            }
            else
            {
                //conflict, add in the head of chain
                temp = (struct HashNode*)malloc(sizeof(struct HashNode));
                temp->index = i;
                temp->next = HT[key].next;
                HT[key].next = temp;
            }
        }
        free_HashTable(HT);
        return result;
    }
    
    int main()
    {
        int numbers[] = {3,-4,-3,9};
        int target = 0;
    
        int *index = twoSum(numbers, sizeof(numbers) / sizeof(numbers[0]), target);
    
        for (int i = 0; i < 2; i++){
            printf("index%d = %d ", i + 1, index[i]);
        }
        printf("\n");
    
        return 0;
    }
    

  • 0
    I

    Hi all,
    I've fixed this. It's because when there's a negative number, the index of the hash table will be negative. For some reason my local environment didn't report this error. Here's the right code.

    By the way, If the OJ shows 'Runtime error'. There's a great chance that some memory-access errors. While 'Time exceed' tends to mean an endless loop.

    #define P 109
     
    struct HashNode{
        int index;
        struct HashNode * next;
    };
    
    void show_HashTable(struct HashNode * HT)
    {
        for (int i = 0 ; i < P ; i++)
        {
            printf("%d ",HT[i].index);
        }
    }
    
    struct HashNode * init_HashTable(struct HashNode* HT)
    {
        HT = (struct HashNode*)malloc(P*sizeof(struct HashNode));
        for (int i = 0 ; i < P ; i++)
        {
            HT[i].index = -1;
            HT[i].next = NULL;
        }
        return HT;
    }
    
    void free_HashTable(struct HashNode* HT)
    {
        struct HashNode* temp1;
        for (int i = 0 ; i < P ; i++)
        {
            temp1 = HT[i].next;
            while (temp1 != NULL)
            {
                struct HashNode* temp2 = temp1->next;
                free(temp1);
                temp1 = temp2;
            }
        }
        free(HT);
    }
    
    int * twoSum(int* nums, int numsSize, int target) {
        int *result;
        result = (int*) malloc(sizeof(int)*2);
        
        struct HashNode* HT;
        HT = init_HashTable(HT);
        // show_HashTable(HT);
        
        for (int i = 0 ; i < numsSize ; i++)
        {
            // printf("iteration %d\n",i);
            struct HashNode * temp;
            int key;
            key = nums[i]%P;
            key = key < 0 ? key+P : key;
            temp = &HT[key];
            while(temp && temp->index != -1)
            {
                if (nums[temp->index] + nums[i] == target)
                {
                    // find the match one
                    result[0] = temp->index;
                    result[1] = i;
                    // show_HashTable(HT);
                    // printf("%d %d", result[0],result[1]);
                    free_HashTable(HT);
                    return result;
                }
                temp = temp->next;
            }
            // no element matchs, add number to HT, key = remains mod P
            key = (target-nums[i])%P;
            key = key < 0 ? key+P : key;
            if (HT[key].index == -1)
            {
                //doesn't conflict
                HT[key].index = i;
            }
            else
            {
                //conflict, add in the head of chain
                temp = (struct HashNode*)malloc(sizeof(struct HashNode));
                temp->index = i;
                temp->next = HT[key].next;
                HT[key].next = temp;
            }
        }
        free_HashTable(HT);
        return result;
    }
    111

Log in to reply
 

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