[1] Two Sum

因為前一個hard搞錯題意覺得太打擊信心了
就找了個easy的來做
姑且不論我之前才在說執行時間不準的事
因為這次執行起來算是快的XD
覺得溫馨～～～～～
暴力法萬歲～～～～～（這也好意思拿出來講XD?!)

Two Sum
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target) {
    int i,j;
    int *ret = malloc((sizeof(int))*2);
    for (i=0;i<numsSize;i++)
        for(j=i+1;j<numsSize;j++)
            if(nums[i]+nums[j] == target)
            {
                ret[0]= i;
                ret[1]= j;
                return ret;
            }
    return ret;
}

照例看看討論區又有應該要唸的東西了 XD
TBC here...

UPDATE!
就討論區說要用hash 做Orz
不知道為什麼寫起來怎麼看怎麼醜Orz
而且沒有一邊執行看結果來回推的話我根本就寫不出來 T口T
完了一個蛋......

不過輸入量大的時候, hash比暴力法快好多喔...
4ms跟97ms的差異 囧
怎麼辦覺得自己沒天份 QQ

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target) {
    int i,j;
    int max=0;
    int min=0;
    for(i=0;i<numsSize;i++)
    {
        if(nums[i]>0 && nums[i]>max)
            max = nums[i];
        if(nums[i]<0 && nums[i]<min)
            min = nums[i];
    }
    int hashSize;
    hashSize = (max - min) +1;
    hashSize = (hashSize > target)? hashSize: target;

    int *hash = malloc(sizeof(int)*hashSize);
    memset(hash,0,hashSize);
    for(i=0;i<numsSize;i++)
    {
        hash[nums[i]-min] ++;
    }
 
    int *ret = malloc(sizeof(int)*2);
    ret[0]=-1;
    ret[1]=-1;

    int v1,v2;
    for(i=0;i<hashSize;i++)
    {    
        v1=0;
        v2=0;
        if(hash[i]>0)
        {
            int diff = target - (i+min);
            if (diff < hashSize && hash[diff-min] >0)
            {
                v1=i+min;
                v2=diff;
                break;
            }
        }
    }
    for(i=0;i<numsSize;i++)
    {
        if (v1 == nums[i] && ret[0] <0)
            ret[0] =i ;
        else if(v2==nums[i] && ret[1] <0)
            ret[1] = i;
    }
    return ret;
}
如果hash裡面再做linked list的話,
應該可以不要有最後一個迴圈去找v1跟v2的index ?
因為index就可以直接存在hash的欄位裡了
照理說會再加速一些些~

是說又要考慮負數, 又要考慮有同樣的數字在不同的index也太煩了吧！！！（顯示為爆炸）