1.3 leetcode 1 Two Sum

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.

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

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

這題要從未排序的陣列裡找出兩數相加值得於target.

首先，最簡單的方法就是，把所有結果列舉，找出答案，但這複雜度是O(N^2)，很明顯不夠好。 運行結果是252ms

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target) {
     int i=0,j=0;

     if(numsSize == 0)
        return NULL;

     int *ans=(int *)malloc(2*sizeof(int));

     for(i=0; i < numsSize ; i++)
        for(j=(i+1); j < numsSize; j++){
            if(target == nums[i]+nums[j]){
                ans[0]=i;
                ans[1]=j;
                break;
            }
        }

      return ans;
}

解法2: 先把array排序過後，利用頭尾去夾出答案，如果target比加總大，我們就把left向右移(sum變大)，如果target比加總小，我們就把right向左移(sum變小) , 這個解法送出來131ms. 而且有個缺點回傳的array index，可能順序是錯的，不過線上判斷好像不管這個，還可以用hash table去搜尋.

void quickSort(int* nums,int left,int right){

    int i = left;
    int j = right;
    int tmp;
    int pivot;


    if(i>j)
        return;

    pivot=nums[left];

    while(i!=j){

        while(i<j && nums[j] >= pivot)
            j--;

        while(i<j && nums[i]<=pivot)
            i++;

        if(i<j){
            tmp=nums[j];
            nums[j]=nums[i];
            nums[i]=tmp;
        }

    }

    //set pivot to center
    nums[left]=nums[i];
    nums[i] = pivot;

    quickSort(nums,left,i-1);
    quickSort(nums,i+1,right);



}
int* twoSum(int* nums, int numsSize, int target) {
     int left=0,right=(numsSize-1);
     int sum=0;
     int tmp[numsSize];

     if(numsSize == 0)
        return NULL;

     memcpy(tmp,nums,(numsSize*sizeof(int)));

    quickSort(tmp,0,(numsSize-1)); /*先做quick sort*/       

     int *ans=(int *)malloc(2*sizeof(int));
      ans[0]=9999999; /*沒意義的值，只是拿來判斷有沒有設過了*/
      ans[1]=9999999;

     /*去找到排序過後的target index*/ 
     while(left != right){
        sum=tmp[left]+tmp[right];
        if(sum==target){
            break;
        }
        else if(sum > target)  
            right--;
        else if(sum < target)
            left++;
     }
     /*搜尋原本對應的位置*/
     for(int i=0; i<numsSize;i++){
         if(nums[i]==tmp[left] && ans[0]==9999999){
            ans[0]=i;
            continue;
         }        
         if(nums[i]==tmp[right] && ans[1]==9999999)
            ans[1]=i;        
     }


      return ans;
}