Leetcode-217.存在重复元素
题目：给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
示例 1： 输入：nums = [1, 2, 3, 1] 输出：true
示例 2： 输入：nums = [1, 2, 3, 4] 输出：false
我们的思路是，先排序，再遍历判断相邻的两个元素是否相等；
代码语言：javascript复制 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;
}Leetcode-219.存在重复元素Ⅱ
题目：给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
示例 1： 输入：nums = [1, 2, 3, 1], k = 3 输出：true
示例 2： 输入：nums = [1, 0, 1, 1], k = 1 输出：true
我们的大体思路是，定义一个哈希表，将数组中的值存到键key中，用val记录当前key的下标；在遍历数组中，nums[i]都要判断是否已经在哈希表中，即这个数组中是否有相同的元素，若已存在哈希表中，就判断 i 减去这个键key所对应的下标是否小于等于k，若不满足，更新键key的值和它的下标val，若满足，返回true；循环结束证明这个数组不满足条件，返回false；
下面看代码和注释，由于是初次接触哈希表，所以代码是参考官方解题的：
代码语言：javascript复制 //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;
}
