below is a 0ms solution from leetcode
but it actually missed a test case
[50000000,3,2,4,28800,50000000]
100000000
this 0ms submission using a %TABLE_SIZE to shrink the table needed
but collision will happen!!
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
int i = 0;
int j = 0;
int *ret = NULL;
int *returnSize = 2;
for(i = 0 ; i<numsSize ; i++){
for(j = i ; j= 0){
return (key % TABLE_SIZE);
}
else{
key = TWO_COMPLEMENT + key;
return (key % TABLE_SIZE);
}
}
// Our record table definition, an array of M records.
//record_table = (Record *)malloc(sizeof(*record_table)*TABLE_SIZE);
// Insert function. Inserts record at the index determined by the hash
// function. Uses linear probing if already occupied.
void insert(Record *record_table,int value, int index){
int idx = hash(value);
record_table[idx].value = value;
record_table[idx].index = index;
// printf("insert table[%d] : %d, %d\n", idx, value, index);
}
// Search Function. Returns the record with a matching key. Search starts
// at the index determined by the hash function. Uses linear probing until
// the matching key is found. Returns NULL on search miss.
int search(Record *record_table,int value) {
int idx = hash(value);
//printf("search table[%d] : %d,%d\n", idx, record_table[idx].value,record_table[idx].index);
if (record_table[idx].value == value ) {
return record_table[idx].index;
}
else {
return 0;
}
}
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
//using hash of value, index
int complement = 0;
//Record record_table[TABLE_SIZE];
Record *record_table;
record_table = malloc(sizeof(record_table)*TABLE_SIZE);
for(int i = 0; i for every element in array, find complement with target in the rest of the array
/*
int complement = 0;
int *arr;
arr = malloc(sizeof(int)*2);
for(int i = 0; i < numsSize; i++){
arr[0] = i;
complement = target - nums[i];
for(int j = i+1 ; j < numsSize; j++ ){
if(nums[j] == complement ){
arr[1] = j;
*returnSize = 2;
return arr;
}
}
}
*returnSize = 0;
return NULL;
*/
}
Better life with Ubuntu 