隨筆札記

題目

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

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

You can return the answer in any order.

Example 1:

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

Example 2:

Input: nums = [3,2,4], target = 6 Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6 Output: [0,1]

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

}}

解法說明

關鍵細節：

1. 輸入為整數矩陣，但可能為亂序。
2. 不用考慮邊界問題，但回傳前時需要留意 returnSize 也要填寫正確。

在考量到第一點的狀態下，直接採用搜尋法去尋找的時間複雜度最差會為 O(n²)， 如果想要讓時間複雜度降低的話，就需要先評估是否可以把問題拆分。

如果我先宣告一個用於排序的矩陣去接 nums 的資料後再去做排序，那必然要選擇時間複雜度最差也要小於 O（n²），這邊我選用 合併排序法（Merge Sort），他的時間複雜度只需要 n + n log n。接著我們再用 疊代 的方式來逐漸縮小範圍，選擇一個時間複雜度不高的搜尋法去搭配就可以，這邊我選用 二分搜尋法（Binary search）來做搜尋符合條件的，時間複雜度搭配疊代最差的話需要  log（n）+ log（n-1）+ … + 1，到目前為止我們已經可以找到被排序過後想要組合成目標值的兩個 index，最後就是比較未排序的矩陣中是否存在已排序兩個目標 index 的值，存在就把他丟過去到回傳矩陣中，這邊時間複雜度為 n。

1. 先複製相同的矩陣用於 合併排序法（Merge Sort）排序
2. 搭配 疊代 及 二分搜尋法 來尋找已排序中是否存在兩個元素可以組合成目標

這樣總共的時間複雜度將會是 2n + n * log（n）+  log（n）+ log（n-1）+ … + 1 → O（n log n）。

程式碼

int *returnArray;
int *sortedArr;
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    sortedArr = (int*)calloc(numsSize,sizeof(int));
    returnArray = (int*)malloc(sizeof(int)*2);
    int findIdx,returnIdx=0;
    
    for(int index = 0;index < numsSize;index++)
        sortedArr[index] = nums[index];
    
    merge_sort(sortedArr, numsSize);
    
    for(int index = 0;index < numsSize;index++){
        findIdx=binary_search(sortedArr,index+1,numsSize-1,target-sortedArr[index]);
        if(-1 != findIdx){

            for(int j=0;j<numsSize;j++){
                if(sortedArr[index]==nums[j] || sortedArr[findIdx]==nums[j])
                    returnArray[returnIdx++]=j;
            }
            *returnSize = 2;
            return returnArray;
        }
    }
    *returnSize = 0;
    return NULL;
    
}

void merge_sort_recursive(int *arr,int *reg, int start,int end){
    if (start >= end)
        return;
    int len = end - start,mid = (len>>1) + start;
    int startFirst = start,endFirst = mid;
    int startSecond = mid + 1,endSecond = end;
    merge_sort_recursive(arr,reg,startFirst,endFirst); //First part
    merge_sort_recursive(arr,reg,startSecond,endSecond); //Second part
    int index = start;
    while(startFirst <= endFirst && startSecond <= endSecond)
        reg[index++] = arr[startFirst] <= arr[startSecond] ? arr[startFirst++] : arr[startSecond++];
    
    while(startFirst <= endFirst)
        reg[index++] = arr[startFirst++];
    
    while(startSecond <= endSecond)
        reg[index++] = arr[startSecond++];
    
    for(int j=start;j<=end;j++){
        arr[j] = reg[j];
    }
}

void merge_sort(int* nums, int numsSize){
    int reg[numsSize];
    merge_sort_recursive(nums,reg,0,numsSize-1);

}

int binary_search(int *arr,int start,int end, int key)
{
    if(start > end)
        return -1;
    int len = end - start,mid = (len>>1) + start;
    if(arr[mid] > key){
        return binary_search(arr,start,mid-1,key);
    }else if(arr[mid]< key){
        return binary_search(arr,mid+1,end,key);
    }else{
        return mid;
    }
}

_______________________________________________

我們透過閱讀，拼湊出真實世界的面貌，
並在反覆的探索及思維中，打破由自我無知與偏見所建立的籓籬。