紅線的生存日誌

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, and you may not use the same element twice.

Example:

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

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

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

按題意來說是可以很快想到簡單的解法, 就是裏面兩個數字相加起來會等於目標

那麼就直接從最開始嘗試一直往後加就可以 nums[0] +nums[1] , num[0] + nums[2], ... nums[1] + nums[2], nums[1] + nums[3]....

不過題目中有聲明最後會free 掉記憶體,要用malloc 所以 不用的話就會有以下的error (就是手建想試試看)

------------------------------------------------------------------------------------------------------------

如果使用result[2]就會出現
load of null pointer of type 'const int'
使用不夠的空間做例如 malloc(4)
assign value to arrary時就會產生
store to address 0x000002531290 with insufficient space for an object of type 'int'

--------------------------------------------------------------------------------------------------------------

好不管這些error, 如果用以上的方法submit就會有

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

此"正常人"想到的方式能達到141ms, 當然, 很多大大是不能滿足於這個需要使用到 O(n^2) 複雜度的

所以就要用到hash table 的概念, 當中每個hash node 是 value 是原先input值  key 為target - input 

typedef struct HashNode {
    int key;
    int val;
} HashNode;

typedef struct HashMap {
    int size;
    HashNode** storage;
} HashMap;

HashMap* hash_create(int size);
void hash_destroy(HashMap* hashMap);
void hash_set(HashMap* hashMap, int key, int value);
HashNode* hash_get(HashMap* hashMap, int key);

HashMap* hash_create(int size){
    HashMap* hashMap = malloc(sizeof(HashMap));
    hashMap->size = size;
    hashMap->storage = calloc(size, sizeof(HashNode*));
    return hashMap;
}

void hash_destroy(HashMap* hashMap) {
    for(int i=0; i < hashMap->size; i++) {
        HashNode *node;
        if((node = hashMap->storage[i])) {
            free(node);
        }
    }
    free(hashMap->storage);
    free(hashMap);
}

void hash_set(HashMap *hashMap, int key, int value) {
    int hash = abs(key) % hashMap->size;
    int flag = hash;
    HashNode* node;
    while ((node = hashMap->storage[hash])) {
        if (hash < hashMap->size - 1) {
            hash++;
        } else {
            hash = 0;
        }
        if (hash == flag) {
            return;
        }
    }
    node = malloc(sizeof(HashNode));
    node->key = key;
    node->val = value;
    hashMap->storage[hash] = node;
}

HashNode* hash_get(HashMap *hashMap, int key) {
    int hash = abs(key) % hashMap->size;
    int flag = hash;
    HashNode* node;
    while ((node = hashMap->storage[hash])) {
        if (node->key == key) {
            return node;
        }

        if (hash < hashMap->size - 1) {
            hash++;
        } else {
            hash = 0;
        }
        if (hash == flag) {
            break;
        }
    }

    return NULL;
}

int* twoSum(int* nums, int numsSize, int target) {
    HashMap* hashMap;
    HashNode* node;
    int rest, i;
    hashMap = hash_create(numsSize);
    for(i = 0; i < numsSize; i++) {
        rest = target - nums[i];
        node = hash_get(hashMap, rest);
        if (node) {
            int* result = malloc(sizeof(int)*2);
            result[0] = node->val;
            result[1] = i;
            hash_destroy(hashMap);
            return result;
        } else {
            hash_set(hashMap, nums[i], i);
        }
    }
    return NULL;
}