I get a runtime Error on Leetcode No 1(Two Sum)

Question

I used hash table with linear probing to solve this problem. And I tested my code on Visual Studio and get the correct solution. Here is the code:

#define HTCAPACITY 50000

int hash(int key) {
    return key % HTCAPACITY;
}

void htInsert(int *keys, int *values, int key, int value) {
    int index = hash(key);

    while(values[index] >= 0)
        index = (index + 1) % HTCAPACITY;
    keys[index] = key;
    values[index] = value;
}

int htSearch(int *keys, int *values, int key) {
    int index = hash(key);

    while(values[index] >= 0) {
        if(keys[index] == key)
            return values[index];
        index = (index + 1) % HTCAPACITY;
    }
    return -1;
}


int* twoSum(int* nums, int numsSize, int target) {
    int keys[HTCAPACITY] = {0};
    int values[HTCAPACITY];
    memset(values, -1, sizeof(int)*HTCAPACITY);
    int i;
    int value = -1;
    int *indices = (int *)malloc(sizeof(int)*2);
    int complement;

    for(i=0; i<numsSize; i++) {
        complement = target - nums[i];
        if((value = htSearch(keys, values, complement)) != -1) {
            indices[0] = value;
            indices[1] = i;
            return indices;
        } else {
            htInsert(keys, values, nums[i], i);
        }
    }
    return NULL;
}

And the error description here:(sorry i can't copy the message directly) error description

And leetcode told that last executed input is [0, 4, 3, 0] and 0

score 0 · Answer 1 · answered Mar 02 '19 at 11:57

you haven't included the test program, or the exact input to your function. However, I hazard a guess that complement turns out negative.

Your bug is likely your hash function. You use % (remainder operator) for the hash value. % for negative numbers returns a negative number. See Modulo operation with negative numbers

I suspect you're getting a negative key value, which causes the values and keys to reference memory ahead of their allocation.

I get a runtime Error on Leetcode No 1(Two Sum)

1 Answers1