1. Two Sum

https://leetcode.com/problems/two-sum/

Description

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Solution 1 直覺作法

$O$(

$N^2$)

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int* ans= malloc(sizeof(int)*2);
    int i,j;
    for(i =0;i<numsSize;i++){
        for(j=0; j<i;j++){
            if((nums[i]+nums[j])==target){
                ans[0]=j;
                ans[1]=i;
            } 
        }
    }
    *returnSize = 2;
    return ans;
}

Solution 2 Hash Table

$O$(

$N$)

#define Hash_num 1000
struct node {
    long value;
    int index;
    struct node * next;
};

int abs(int n){
    return ((n >> 31) ^ n) - (n >> 31);
}

int searchHash(struct node ** Hashtable, long target, int n){
    int index = abs(target)%n;
    struct node* tmp = Hashtable[index]->next;
    while(tmp){
        if(tmp->value == target){
            return tmp->index;
        }
        tmp=tmp->next;
    }
    return -1; //-1 for not find
}
void addHash(struct node** Hashtable, int value, int index, int n){
    int hash_i = abs(value)%n;
    struct node * tmp = Hashtable[hash_i];
    struct node * new = malloc(sizeof(struct node));
    new->value = value;
    new->index = index;
    new->next = tmp->next;
    tmp->next = new;
    //printf("ADD : %d\n",value);
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int i=0,j=0;
    int * ans;
    int status=0;
    if(!nums||!numsSize)
        return 0;
    *returnSize =0;
    //build hash table
    struct node** Hashtable = malloc(Hash_num*sizeof(struct node*));
    //Hash Table initial
    for(i=0;i<Hash_num;i++){
        Hashtable[i] = calloc(1,sizeof(struct node));
        Hashtable[i]->next = NULL;
    }
    for(int i=0; i<numsSize; i++){
        //find target in hash table, if doesn't find ->add in hash table
        status = searchHash(Hashtable, target-nums[i], Hash_num);
        //printf("%d\n", status);
        if(status!=-1){
            ans=malloc(sizeof(int)*2);
            ans[0]=status;
            ans[1]=i;
            *returnSize=2;
        }
        else{
            //add in hash table
            addHash(Hashtable, nums[i],i,Hash_num);
        }
    }
    return ans;
}