# 217. Contains Duplicate

題目：<https://leetcode.com/problems/contains-duplicate/>

解法：直接解，使用 set 來判斷重複，python 使用內建的型態，C 使用 leetcode 額外支援的型態 uthash。

Python3：

class Solution:
    def containsDuplicate(self, nums: list[int]) -> bool:
        hashSet = set()
        for num in nums:
            if num in hashSet:
                return True
            hashSet.add(num)
        return False

if __name__ == '__main__':
    nums = [1, 2, 3, 4]

    ans = Solution().containsDuplicate(nums)
    print(ans)

C：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "uthash.h"

typedef struct {
    int id;
    UT_hash_handle hh;
} hashEntry;

hashEntry *hashSet = NULL;

void hashSetAdd(int id) {
    hashEntry *e;
    HASH_FIND_INT(hashSet, &id, e);
    if (e == NULL) {
        e = (hashEntry*)malloc(sizeof(hashEntry));
        e->id = id;
        HASH_ADD_INT(hashSet, id, e);
    }
}

bool hashSetContains(int id) {
    hashEntry *e;
    HASH_FIND_INT(hashSet, &id, e);
    return (e != NULL);
}

void hashSetRemove(int id) {
    hashEntry *e;
    HASH_FIND_INT(hashSet, &id, e);
    HASH_DEL(hashSet, e);
    free(e);
}

void hashSetFree() {
    hashEntry *cur;
    hashEntry *tmp;

    HASH_ITER(hh, hashSet, cur, tmp) {
        HASH_DEL(hashSet, cur);
        free(cur);
    }
}

void hashSetPrint()
{
    hashEntry *e;
    for (e = hashSet; e != NULL; e = (hashEntry*)(e->hh.next)) {
        printf("id %d\n", e->id);
    }
    printf("\n");
}

bool containsDuplicate(int* nums, int numsSize) {
    hashSetFree();
    for (int i = 0; i < numsSize; i++) {
        if (hashSetContains(nums[i]))
            return true;
        hashSetAdd(nums[i]);
    }
    return false;
}

int main()
{
    int nums[] = {1, 2, 3, 4};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    
    bool ans = containsDuplicate(nums, numsSize);
    printf("%s\n", ans ? "True" : "False");

    hashSetFree();
    return 0;
}

###### tags: `leetcode` `hash table`