【leetcode面试经典150题】46. 存在重复元素 II（C++）

【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主，题解使用C++语言。（若有使用其他语言的同学也可了解题解思路，本质上语法内容一致）

【题目描述】

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

【示例一】

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

【示例二】

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

【示例三】

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

【提示及数据范围】

• 1 <= nums.length <= 10的5次方
• -10的9次方 <= nums[i] <= 10的9次方
• 0 <= k <= 10的5次方

【代码】

// 方法一：哈希表
 
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int,int> dictionary;
        int length = nums.size();
        for(int i = 0;i<length;i++){
            int num = nums[i];
            if(dictionary.count(num) && i - dictionary[num] <= k) return true;
            dictionary[num] = i;
        }
        return false;
    }
};
 
// 方法二：滑动窗口
 
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_set<int> s;
        int length = nums.size();
        for (int i = 0; i < length; i++) {
            if (i > k) {
                s.erase(nums[i - k - 1]);
            }
            if (s.count(nums[i])) {
                return true;
            }
            s.insert(nums[i]);
        }
        return false;
    }
};