【Leetcode -217.存在重复元素 -Leetcode-219.存在重复元素Ⅱ】

		int compare(const void* p1, const void* p2)
		{
		    return *(int*)p1 - *(int*)p2;
		}
		
		bool containsDuplicate(int* nums, int numsSize)
		{
		    qsort(nums, numsSize, sizeof(nums[0]), compare);
		    for (int i = 0; i < numsSize - 1; i++)
		    {
		        if (nums[i] == nums[i + 1])
		        {
		            return true;
		        }
		    }
		    return false;
		}

		//UT_hash_handle是头文件"uthash.h"中定义的，使得这个结构体具有哈希表的性质
		//HashEntry结构体是自定义的
		struct HashEntry
		{
		    int key;    //键
		    int val;    //下标
		    UT_hash_handle hh;  //使得这个结构体具有哈希表的性质
		};
		
		void hashAddItem(struct HashEntry** obj, int key, int val)
		{
		    struct HashEntry* pEntry = (struct HashEntry*)malloc(sizeof(struct HashEntry));
		    pEntry->key = key;
		    pEntry->val = val;
		
		    //添加键key为int类型
		    //*obj是哈希表
		    //key是键名称字段
		    //pEntry是指向需要增加的结构的指针，其实pEntry就是一个哈希桶
		    HASH_ADD_INT(*obj, key, pEntry);
		    
		}
		
		struct HashEntry* hashFindItem(struct HashEntry** obj, int key)
		{
		    struct HashEntry* pEntry = NULL;
		
		    //*obj为哈希表
		    //&key是键的地址
		    //pEntry是返回的指针的类型，如果没有找到则返回NULL；如果找到就返回该key所在哈希桶的地址返回去
		    HASH_FIND_INT(*obj, &key, pEntry);
		    
		    return pEntry;
		}
		
		void hashFreeAll(struct HashEntry** obj)
		{
		    struct HashEntry* curr, * next;
		
		    //循环删除
		    //第一个参数是hh，第二个为哈希表，第三个和第四个是用来循环的指针
		    //curr指针是指向哈希表的头结点的，next指针就是curr的next指针，一直循环下去，直到哈希表的尾部
		    HASH_ITER(hh, *obj, curr, next)
		    {
		        //HASH_DEL的第二个参数curr为指向需要删除键的结构指针，
		        //可以直接看作是链表的删除，删除链表首先需要找到指向该链表的指针
		        HASH_DEL(*obj, curr);
		        free(curr);
		    }
		}
		
		bool containsNearbyDuplicate(int* nums, int numsSize, int k)
		{
		    //初始化为空指针，相当于初始化为0
		    struct HashEntry* dictionary = NULL;
		
		    for (int i = 0; i < numsSize; i++)
		    {
		        //这里用一个结构体指针接收HASH_FIND_INT的返回值
		        struct HashEntry* pEntry = hashFindItem(&dictionary, nums[i]);
		
		        //若pEntry为空，说明这个键不在哈希表中，不进入if语句
		        //当pEntry不为空，即key这个键已经存在哈希表中
		        //当pEntry不为空，还要判断i减去当前存在的key对应的下标的值是否小于等于k
		        if (pEntry != NULL && i - pEntry->val <= k)
		        {
		            //删除哈希表
		            hashFreeAll(&dictionary);
		            return true;
		        }
		
		        //当pEntry为空，或者不满足，nums[i]覆盖当前的key，并更新当前的val（下标）
		        hashAddItem(&dictionary, nums[i], i);
		    }
		
		    //删除哈希表
		    //当循环结束不返回，说明都不满足条件，返回false
		    hashFreeAll(&dictionary);
		    return false;
		}