题目:给你一个整数数组 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;
}
题目:给你一个整数数组 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;
}