【LeetCode219】存在重复元素 II(哈希表)

简介: 哈希。mp[i]=j表示数字i在原数组的下标。一次遍历判断即可。PS:unordered_map的mp.find(value)返回的是value对应的key值。

一、题目


image.png

二、思路和代码

哈希。mp[i]=j表示数字i在原数组的下标。一次遍历判断即可。

PS:unordered_map的mp.find(value)返回的是value对应的key值。


一开始这样提交,发现下面的方法有3个测试用例没过,比如[1, 0, 1, 1] k = 1这种情况,发现正确应该是返回true的,但是这样的方法会只判断了第0个1和第2个1这两个位置(没有判断最后两个1的情况),是因为没有更新哈希表中key对应的value的最新值导致的。

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        //mp[i]=j表示数字i在原数组的下标
        unordered_map<int, int>mp;
        int temp;
        for(int i = 0; i < nums.size(); i++){
            //存在nums[i]为key的kv
            if(mp.count(nums[i])){
                temp = abs(mp[nums[i]] - i);
                if(temp <= k){
                    return true;
                }
            }else{//之前没有遍历过这个数字
                mp[nums[i]] = i;
            }
        }
        return false;
    }
};

所以在判断哈希表存在nums[i]时,最后同样需要进行更新,即在if内加上mp[nums[i]] = i;

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        //mp[i]=j表示数字i在原数组的下标
        unordered_map<int, int>mp;
        int temp;
        for(int i = 0; i < nums.size(); i++){
            //存在nums[i]为key的kv
            if(mp.count(nums[i])){
                temp = abs(mp[nums[i]] - i);
                if(temp <= k){
                    return true;
                }
                mp[nums[i]] = i;  //一开始漏了这句,因为要更新!!
            }else{//之前没有遍历过这个数字
                mp[nums[i]] = i;
            }
        }
        return false;
    }
};

image.png


感谢柳小葱大佬~补充python解法,enumerate获取索引和数值后,用字典dic的key存储数值, value存储索引,一次for遍历四行代码搞定:

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        dic = {}
        # dic的key为数值, value为索引
        for key, v in enumerate(nums):
            if v in dic and key - dic[v] <= k:
                return True
            dic[v] = key
        return False
相关文章
|
12月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
132 1
|
6月前
|
机器学习/深度学习 存储 算法
【LeetCode 热题100】347:前 K 个高频元素(详细解析)(Go语言版)
这篇文章详细解析了力扣热题 347——前 K 个高频元素的三种解法:哈希表+小顶堆、哈希表+快速排序和哈希表+桶排序。每种方法都附有清晰的思路讲解和 Go 语言代码实现。小顶堆方法时间复杂度为 O(n log k),适合处理大规模数据;快速排序方法时间复杂度为 O(n log n),适用于数据量较小的场景;桶排序方法在特定条件下能达到线性时间复杂度 O(n)。文章通过对比分析,帮助读者根据实际需求选择最优解法,并提供了完整的代码示例,是一篇非常实用的算法学习资料。
364 90
|
12月前
【LeetCode 27】347.前k个高频元素
【LeetCode 27】347.前k个高频元素
116 0
|
索引
力扣随机一题 6/26 哈希表 数组 思维
力扣随机一题 6/26 哈希表 数组 思维
99 0
|
存储 算法
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法,使用双指针技术在原链表上原地删除重复元素,提供了一种时间和空间效率都较高的解决方案。
LeetCode第83题删除排序链表中的重复元素
【LeetCode 06】203.移除链表元素
【LeetCode 06】203.移除链表元素
86 0
【LeetCode-每日一题】移除元素
【LeetCode-每日一题】移除元素
87 0
|
算法 索引
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
这篇文章介绍了LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"的解题方法,通过使用双指针法从数组两端向中间同时查找目标值,有效地找到了目标值的首次和最后一次出现的索引位置。
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
|
Python
【Leetcode刷题Python】剑指 Offer II 082. 含有重复元素集合的组合
解决LeetCode平台《剑指 Offer II 082. 含有重复元素集合的组合》题目的Python代码实现,通过深度优先搜索算法找出所有和为特定目标值的数字组合,并在搜索过程中通过排序和跳过重复元素来避免解集中出现重复组合。
107 2
力扣随机一题 哈希表 排序 数组
力扣随机一题 哈希表 排序 数组
85 1

热门文章

最新文章