LeetCode 219.存在重复元素 II

目录

题目：

题目描述：

题目链接：

思路：

核心思路：

思路详解：

代码：

C++代码：

Java代码：

---

题目：

题目描述：

题目链接：

219. 存在重复元素 II - 力扣（LeetCode）

思路：

核心思路：

哈希表（Map）

思路详解：

Map存的是键值对，这题键存的是数组中的元素值，值存的是该元素值的最新索引（下标），时间复杂度为O(n)。遍历整个数组把每一个元素和它的索引存入Map，每次存入一个元素先调用containsKey判断Map中是否存在相同的键值，如果存在再判断这个相同元素不同索引差值的绝对值是否<=k，只要存在一对满足要求就可以马上return true;退出。如果不满足就把这个键值对存入Map（该键不存在就是新存入的键值对，键已经存在就是更新最新索引）。如果已经遍历完数组全部元素都没有满足要求的，就返回false

代码：

C++代码：

class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_map<int,int> mp;for(int i=0;i<nums.size();i++){//由于unordered_map不允许存储具有重复键的元素，因此count函数基本上用于//检查unordered_map中是否存在带有给定键的元素if(mp.count(nums[i])&&abs(i+1-mp[nums[i]]<=k)){return true;}mp[nums[i]]=i+1;}return false;}
};

Java代码：

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