[leetcode]: 219. Contains Duplicate II

- 日理万妓 2022-06-15 12:47 141阅读 0赞

# 1.题目 #

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums\[i\] = nums\[j\] and the absolute difference between i and j is at most k.

给一个数组A和整数k，判断数组中是否存在两个相同元素并且下标距离不大于k

# 2.分析 #

两种方法  
**方法1**  
使用unordered\_map建立哈希表存储出现的数字及其下标。  
遍历一遍数组，对于当前元素，查找哈希表中是否已经出现过该元素并计算下标差是否<=k

**方法2**  
使用unorder\_set存储最近k个元素。  
遍历一遍数组，对于当前元素，如果插入set中失败说明前面k个元素中已经存在当前元素，返回true。

# 3.代码 #

使用unordered\_map 存储元素值及其下标

class Solution {
    public:
        bool containsNearbyDuplicate(vector<int>& nums, int k) {
            unordered_map<int, int> hashMap;
            for (int i = 0; i < nums.size(); i++) {
                if (hashMap.find(nums[i]) != hashMap.end())//相同元素
                    if (i + 1 - hashMap[nums[i]] <= k)//下标间隔小于等于k
                        return true;
                    else
                        hashMap[nums[i]] = i + 1;
                else
                    hashMap[nums[i]] = i + 1;
            }
            return false;
        }
    };

使用unordered\_set 存储最近k个元素

class Solution {
    public:
       bool containsNearbyDuplicate(vector<int>& nums, int k) {
            unordered_set<int> nearK;
            for (int i = 0; i < nums.size(); i++) {
                if (i > k)//set里面存储当前元素的前面k个元素
                    nearK.erase(nums[i - k - 1]);
                if (!nearK.insert(nums[i]).second)//插入失败，说明已经存在该元素
                    return true;
            }
            return false;
        }
    };