leetcode 219. 存在重复元素 II

落日映苍穹つ 2023-09-26 11:34 22阅读 0赞

给你一个整数数组 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\] <= 109  
0 <= k <= 105

代码：

class Solution {
        
    public:
        bool containsNearbyDuplicate(vector<int>& nums, int k) {
        
            unordered_map<int,int> hashtable;
            int n=nums.size();
            for(int i=0;i<n;++i){
        
                if(hashtable.count(nums[i])==0)//如果没有找到就放入哈希表中
                    hashtable.insert({
        nums[i],i});
                else{
        
                    if(abs(i-hashtable[nums[i]])<=k)//如果它们的下标差大于k就可以返回true
                        return true;
                    else//如果小于k，说明当前与之相等的元素和上一个元素距离很远，那么在这个元素
                    	//后面的元素就离得更远，所以后面的更不可能差小于k，所以将当前的下标替换之前的下标，
                    	//这样就可以判断后面是否有相同元素的下标差小于k了
                        //hashtable.insert({nums[i],i});  //我这样写的目的也是想下标更新，但是这样不能更新value的值，下面的可以
                        hashtable[nums[i]]=i;
                }
            }
            return false;
        }
    };

关于 [C++ map容器插入具有相同键的键值对的覆盖问题][C_ map] 可以看这篇文章

[C_ map]: https://blog.csdn.net/zmhzmhzm/article/details/108587959?ops_request_misc=&request_id=&biz_id=102&utm_term=unordered_map%E6%94%BE%E5%85%A5%E9%87%8D%E5%A4%8D%E7%9A%84%E9%94%AE%E5%80%BC%E4%BC%9A%E6%80%8E%E4%B9%88%E6%A0%B7&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-3-108587959.142%5Ev56%5Enew_blog_pos_by_title,201%5Ev3%5Econtrol_2&spm=1018.2226.3001.4187