Leetcode-217.存在重复元素
题目：给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
示例 1：
输入：nums = [1, 2, 3, 1]
输出：true
示例 2：
输入：nums = [1, 2, 3, 4]
输出：false
我们的思路是，先排序，再遍历判断相邻的两个元素是否相等；
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；
下面看代码和注释，由于是初次接触哈希表，所以代码是参考官方解题的：
//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; }
