「优选算法刷题」：存在重复元素Ⅱ

一、题目

给你一个整数数组 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

二、思路解析

本题还有一道同类题《存在重复元素》，搭配阅读效果更佳哦，链接：http://t.csdnimg.cn/ZHBBN

回到这道题上来。不算复杂，利用哈希表来存储元素及其对应的索引，然后在遍历数组的过程中进行查找和比较即可。

相较于上一道同类题，本题多了如下判断：

在遍历数组nums的过程中，对于每个元素nums[i]，先检查哈希表中是否已经包含该元素，如果包含，再判断当前索引i与哈希表中存储的索引的差值是否小于等于k，如果是，则返回true；否则，更新哈希表中该元素的索引为当前索引i。

最后，如果遍历完整个数组都没有找到符合条件的索引对，则返回false。

还有一点不同之处，上一道题我用的容器是 HashSet ， 因为只需要一个键 Key 即可；而这道题既需要键 Key 又需要值 Value ，所以我用的是 HashMap 。

三、完整代码

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> hash = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(hash.containsKey(nums[i])){
                if(i - hash.get(nums[i]) <= k)
                return true;
            }
            hash.put(nums[i],i);
        }
        return false;
    }
}

以上就是本篇博客的全部内容啦，如有不足之处，还请各位指出，期待能和各位一起进步！

原文地址：https://blog.csdn.net/C_Small_Cai/article/details/136279851

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！