LeetCode 1 - Two Sum

tags: 每日一LeetCode爆肝又爆頭

Description

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Link

• https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/submissions/

Version 1.0 - loop

int* twoSum(int* nums, int numsSize, int target, int* returnSize)
{
    int i = 0; 
    int j = 0;
    int value = 0;
    bool found = false;
    
    for( i = 0; i < numsSize; i++){
        value = target - nums[i];
        for(j = i + 1; j < numsSize; j++){
            if(nums[j] == value){
                found = true;
                break;
            }
        }
        if(found)
            break;
    }
    
    if(!found)
        return NULL;
    
    *returnSize = 2;
    int *ret = malloc(sizeof(int)* *returnSize);
    ret[0] = i;
    ret[1] = j;
    
    return ret;
}

Version 2.0 - Using Hash Table

• BKDR Hash
• Murmur hash

Version 3.0 - Using qsort & bsearch

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

struct recored {
    int index;
    int value;
};

struct recored *data = NULL;

static int compare(void const*a, void const*b)
{
    return ((struct recored const*)a)->value - 
           ((struct recored const*)b)->value;
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize)
{

    int i = 0;
    struct recored * found = NULL;
    struct recored _target;
    
    data = malloc(sizeof(struct recored) * numsSize);  
    for(i = 0; i < numsSize; i++){
        data[i].index = i;
        data[i].value = nums[i];
    }
    
    qsort(data, numsSize, sizeof(struct recored), compare);
    
    for( i = 0; i < numsSize; i++){
        _target.value = target - nums[i];
        found = bsearch(&_target, data, numsSize,
                        sizeof(struct recored), compare);
                        
        if(NULL != found && found->index != i){
            break;
        }
    }
    
    *returnSize = 2;
    int *ret = malloc(sizeof(int)* *returnSize);
    ret[0] = i;
    ret[1] = found->index;
  
    return ret;
}