two sum(2)

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;
    */

}

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com 標誌

您的留言將使用 WordPress.com 帳號。 登出 /  變更 )

Google photo

您的留言將使用 Google 帳號。 登出 /  變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 /  變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 /  變更 )

連結到 %s