219.存在重复元素II

链接：219.存在重复元素II
难度：Easy
标签：数组、哈希表、滑动窗口
简介：给定一个整数数组和一个整数  k，判断数组中是否存在两个不同的索引  i  和  j，使得  nums [i] = nums [j]，并且 i 和 j  的差的 绝对值 至多为 k。

题解 1 - c

• 编辑时间：2021-11-30
• 执行用时：140ms
• 内存消耗：42.4MB
• 编程语言：c
• 解法介绍：哈希表存储值和下标。

typedef struct hashTable{
    int key;
    int idx;
    UT_hash_handle hh;
} hashTable;
bool containsNearbyDuplicate(int* nums, int numsSize, int k){
    hashTable* map = NULL;
    for (int i = 0; i < numsSize; i++) {
        hashTable* temp = NULL;
        HASH_FIND_INT(map, &nums[i], temp);
        if (temp) {
            if (i - temp->idx <= k) return 1;
            else temp->idx = i;
        } else {
            temp = (hashTable*)malloc(sizeof(hashTable));
            temp->key = nums[i];
            temp->idx = i;
            HASH_ADD_INT(map, key, temp);
        }
    }
    return 0;
}

题解 2 - cpp

• 编辑时间：2022-01-19
• 执行用时：188ms
• 内存消耗：75.3MB
• 编程语言：cpp
• 解法介绍：哈希存储。

class Solution {
   public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> m;
        for (int i = 0; i < nums.size(); i++) {
            if (m.count(nums[i]) && i - m[nums[i]] <= k) return 1;
            m[nums[i]] = i;
        }
        return 0;
    }
};