# Leetcode 1. Two Sum 筆記
## 暴力解
一般最直覺可以想到的方式，題目有規定要使用動態記憶體配置，所以這邊使用malloc來製作，C語言中動態記憶體配置有關的函數有malloc、calloc、realloc、free。

當程式需要使用到大量記憶體的時候就必須宣告它，例如你不知道可能要用到多大空間的array這時候宣告它就不會導致切一大塊記憶體卻沒有用到，造成演算法效能低落。

> malloc全名memory allocation，配置size bytes 的記憶體區塊，會回傳一個指向該記憶體開頭的指標
> calloc全名contiguous allocation，配置array用，一樣回傳一個指向該記憶體開頭的指標
> realoc就用來改變空間大小
> free非常重要，要用來釋放空間

[動態記憶體的相關測試](https://morosedog.gitlab.io/C-20191024-C-20/)
[微軟官方文件](https://docs.microsoft.com/zh-tw/cpp/c-runtime-library/reference/malloc?view=msvc-170)

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

執行時間200ms，大小6.5MB
## HashTable
以key-value方式表示，透過下圖可以看到為一種mapping關係，如果今天將n個數字先儲存在hash table中，要判斷數字是否有沒有在Hash Table裡，只要通過hash function就可以快速獲得數字是否有儲存，但要注意value值是否夠用，如果key太多就會有多個指到同個value的問題。


稍微介紹一下三元運算子

A?B:C 若A為真，則B，若A為否，則C

這題解法當迴圈跑到nums[i]時，如果 target-nums[i]還不在 Hash Table中，那就儲存(nums[i], i)，這樣就完成這題的演算法了

#define SIZE 30000 //這數字能跑過

int hashtable(int key)//建立hashtable
{
    int r = key % SIZE;
    return r < 0 ? r + SIZE : r;//hash function
}

void insert(int *keys, int *values, int key, int value)//插值
{
    int index = hashtable(key);

    while (values[index])
    {
        index = (index + 1) % SIZE;
    }

    keys[index] = key;
    values[index] = value;
}

int search(int *keys, int *values, int key)//進行搜尋
{
    int index = hashtable(key);

    while (values[index])
    {
        if (keys[index] == key)
        {
            return values[index];
        }

        index = (index + 1) % SIZE;
    }

    return 0;
}
int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
    *returnSize = 2;
    int keys[SIZE];
    int values[SIZE] = {0};

    for (int i = 0; i < numsSize; i++)
    {
        int complements = target - nums[i];
        int value = search(keys, values, complements);

        if (value)
        {
            int *result = (int *)malloc(sizeof(int) * 2);
            result[0] = value - 1;
            result[1] = i;
            return result;
        }

        insert(keys, values, nums[i], i + 1);
    }

    return NULL;
}

執行時間15ms，6.3MB

###### tags: `LeetCode`