219. Contains Duplicate II

[Shawngbk]

保持集合中k间隔中的数不符合题目中的条件，例如｛1，2，3，4，1｝k＝1，即使有相同元素，也要返回false public class Solution { public boolean containsNearbyDuplicate(int[] nums, int k) { HashSet set = new HashSet<>(); for(int i = 0; i < nums.length; i++) { if(set.contains(nums[i])) { return true; } else { set.add(nums[i]); } if(i - k >= 0) set.remove(nums[i-k]); } return false; } }

[Shawngbk]

airbnb palantir

[Shawngbk]

//O(n) public boolean containsNearbyDuplicate(int[] nums, int k) { if(nums.length == 0 || k == 0) return false; HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); for(int i = 0; i < nums.length; i++){ if(!map.containsKey(nums[i])){ map.put(nums[i],i); }else{ if(i - map.get(nums[i]) <= k) return true; map.put(nums[i],i); //update the index of nums[i], always have the most recent index } } return false; }