一、题目
二、思路和代码
哈希。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; } };
感谢柳小葱大佬~补充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
