个人主页：C++忠实粉丝
欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创哈希表(4)_存在重复元素II_面试题
收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记，欢迎大家在评论区交流讨论💌
目录
1. 题目连接
2. 题目描述
3. 解法
算法思路:
代码展示:
1. 题目连接
OJ链接 : 存在重复元素II 
https://leetcode.cn/problems/contains-duplicate-ii/description/
2. 题目描述
给你一个整数数组 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
示例 3：
输入：nums = [1,2,3,1,2,3], k = 2 输出：false
提示：
1 <= nums.length <= 105-109 <= nums[i] <= 1090 <= k <= 105
3. 解法
算法思路:
解决该问题需要我们快速定位到两个信息：
• 两个相同的元素；
• 这两个相同元素的下标。
因此，我们可以使用「哈希表」，令数组内的元素做 key 值，该元素所对应的下标做 val 值，将「数组元素」和「下标」绑定在⼀起，存入到「哈希表」中。
如果数组内存在大量的「重复元素」，而我们判断下标所对应的元素是否符合条件的时候，需要将不同下标的元素作比较，怎么处理这个情况呢？
答：这里运用了一个「小贪心」。
我们按照下标「从小到大」的顺序遍历数组，当遇到两个元素相同，并且比较它们的下标时，这两个下标⼀定是距离最近的，因为：
• 如果当前判断符合条件直接返回 true ，无需继续往后查找。
• 如果不符合条件，那么前一个下标⼀定不可能与后续相同元素的下标匹配（因为下标在逐渐变
大），那么我们可以大胆舍去前⼀个存储的下标，转而将其换成新的下标，继续匹配。
通俗易懂来说, 就是如果前面重复元素符合要求, 那离它最近的元素一定符合要求~~
代码展示:
class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_map<int, int> hash;for(int i = 0; i < nums.size(); i++){if(hash.count(nums[i])) if(i - hash[nums[i]] <= k) return true;hash[nums[i]] = i;}return false;}
};
