[219] Contains Duplicate II

先暫存一下，應該是對的，但是會超時 （那就是不對好嗎XD！）

看起來要用hash table

沒想到時至今日C也有現成的hash table 可以用了！

但因為要花腦力想一下，今天先不用這個，純紀錄我的超時版本XD

bool containsNearbyDuplicate(int* nums, int numsSize, int k){

    if (k==0)

        return false;

    for (int i=0; i <numsSize-1;i++)

    {

        for (int j=1;j<=k;j++)

        {

//printf(" %d %d %d\n", i,j,k);

            if (i+j >= numsSize)

                break;

            if (nums[i]==nums[i+j])

                return true;

            

        }

    }

    return false;

}

好，我讀完了 hash table然後邊抄邊寫用完了。

但冷靜看了解答發現因為測資不算超爆幹大，其實可以土炮hash table ?!

想說那土砲也來寫一次好了，但寫寫又卡住了 XD 超過一筆的相同數值怎麼辦？！

原來！！！因為要小於等於k，其實hash table 裡最多就是只紀錄一筆，當第二筆進來而index 相減還大於k的時候，由於我們是遞增下去掃的，這個範圍的value顯然不符合，前一個記下來的index 也沒有用了，所以把index值更新之後，再繼續往下面找，看後面有沒有人符合。

那就先不再寫一次了吧 XD 大家都好聰明啊～～（遠目）

struct hash_struct{

    int id;

    int value;

    UT_hash_handle hh;

};

bool containsNearbyDuplicate(int* nums, int numsSize, int k){

    struct hash_struct *hash=NULL;

    for (int i=0;i<numsSize; i++)

    {

        struct hash_struct *tmp=NULL;

        HASH_FIND_INT( hash, &nums[i], tmp );  

        if (tmp == NULL)

        {

            tmp=malloc (sizeof (struct hash_struct)*1);

            tmp->id= nums[i];

            tmp->value=i;

            HASH_ADD_INT(hash, id ,tmp);

        }

        else

        {

            if (i-(tmp->value)<=k)

                return true;

            else

            

        }

    }

    return false;

}