yoruru的努力日記

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]

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

SOL：

這一題我實作了三個解法，分別如下：

解法一、用兩個loop的暴力解

空間複雜度：O(1)
時間複雜度：O(n²)

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

解法二、先依大小排序(但須記得數字原本的位置)，然後用binary search左右指標 l,r 來解，若找到相加符合target，則回傳；其餘的話，如果 (nodes[l].val + nodes[r].val)>target，則右指標 r 變小；否則左指標 l 變大。

空間複雜度：O(2n)
時間複雜度：O(nlogn)

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
struct node{
    int val;
    int idx;
};
int cmp(const void* p1, const void* p2){
    return ( ((struct node*)p1)->val - ((struct node*)p2)->val );
}
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    struct node* nodes = (struct node*)malloc(sizeof(struct node)*numsSize);
    for(int i = 0; i<numsSize; i++){
        nodes[i].val = nums[i];
        nodes[i].idx = i;
    }
    qsort(nodes,numsSize,sizeof(nodes[0]),cmp);
    int l=0, r=numsSize-1;
    int *result=NULL;
    *returnSize =0;
    while(l<=r){
        if((nodes[l].val + nodes[r].val)==target){
            *returnSize = 2;
            result = (int*)malloc(sizeof(int)*2);
            result[0]=nodes[l].idx;
            result[1]=nodes[r].idx;
            free(nodes);
            return result;
        }
        else if((nodes[l].val + nodes[r].val)>target)
            r--;
        else
            l++;
    }
    free(nodes);
    return result;
}

從結果可以很明顯看出，就是用空間換時間。

解法三、用hash table紀錄所有的值，可以用想要的值去找出idx，hash table的核心在於每次查找都是O(1)。

思路：(來自 Leetcode 1. Two Sum (C/Python3) @brad84622)

1.掃一次nums，先找max,min
2.建一個新的array大小為max-min+1(缺點是max跟min差很大的話，會很浪費空間),初始化成0, offset=min(偏移量基準)
3.再掃一次填表 若值x,就把他在nums的index填入arr[x-offset]這格
4.開始找值,首先讀數值a,去hashTable內找target-a這個值，也就是直接存取 arr[target-a-offset] 這格看index多少
5.找到值就放進result[0],result[1],且值不能相同,回傳result之前記得釋放hashTable的記憶體空間,最後回傳result。

空間複雜度：O(max-min+1)
時間複雜度：O(n)

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int MIN = nums[0];
    int MAX = nums[0];
    *returnSize = 2;
    int *result = (int*)malloc(sizeof(int)*(*returnSize));
    for(int i = 0; i<numsSize; i++){
        MAX = (nums[i] > MAX) ?  nums[i] : MAX;
        MIN = (nums[i] < MIN) ?  nums[i] : MIN;
    }
    int *hashTable = (int*)malloc(sizeof(int)*(MAX-MIN+1));
    memset(hashTable,-1,sizeof(int)*(MAX-MIN+1));
    for(int i = 0; i<numsSize; i++){
        hashTable[nums[i]-MIN]=i;
    }
    for(int i = 0; i<numsSize; i++){
        int findidx = target - nums[i] - MIN;
        if((findidx)>=0 && (findidx)<=(MAX-MIN) && hashTable[findidx]>-1 && hashTable[findidx]!=i){
            result[0]=i;
            result[1]=hashTable[findidx];
            free(hashTable);
            return result;
        }
    }
    *returnSize = 0;
    result = NULL;
    return result;
}

但我的寫法無論時間或空間都表現得很差，即使註解掉把hashtable都賦值，也只讓執行時間上升到打敗20%左右而已。

// memset(hashTable,-1,sizeof(int)*(MAX-MIN+1));

不過同樣的程式過了半個月後執行，就突然變好了。(看來果然是參考而已

hash table的寫法也可以參考這篇提到的 [Leetcode] C語言合集(LC1、LC121、LC242)，真的實作 hash table 的功能，可以降低空間複雜度。