[LeetCode] 219. 存在重复元素 II

[Animenzzzz]

题目描述：

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。

示例 1:

输入: nums = [1,2,3,1], k = 3
输出: true

示例 2:

输入: nums = [1,0,1,1], k = 1
输出: true

示例 3:

输入: nums = [1,2,3,1,2,3], k = 2
输出: false

解题思路：使用哈希表，一次遍历就够了。需要注意的地方：如果遇到比k小的间距，直接return true就好，如果遇到比k还大的间距，需要更新好k_index的值，防止之后还会遇到此重复的值且小于k间距。

C解题：

struct HashMap {
    int number;
    int k_index;
    UT_hash_handle hh;
};
bool containsNearbyDuplicate(int* nums, int numsSize, int k){
    struct HashMap *hashmap = NULL,*hashtmp = NULL;
    for (int i = 0; i < numsSize; i++)
    {
        HASH_FIND_INT(hashmap,&nums[i],hashtmp);
        if (hashtmp){
            if(i-hashtmp->k_index <= k){
                return true;
            }else{
                hashtmp->k_index = i;
            }
        }
        else{
            struct HashMap *tmp = (struct HashMap*)malloc(sizeof(struct HashMap));
            tmp->number = nums[i];
            tmp->k_index = i;
            HASH_ADD_INT(hashmap,number,tmp);
        }
    }
    return false;
}