LeetCode 219 存在重复元素||

1.线性搜索

class Solution { public boolean containsNearbyDuplicate(int[] nums, int k) { for(int i=0;i<nums.length;i++){ for(int j=i+1;j<nums.length&&j<=i+k;j++){ if(nums[i]==nums[j]) return true; } } return false; } }

这时间复杂度让我想哭 

2.散列表

class Solution { public boolean containsNearbyDuplicate(int[] nums, int k) { Set<Integer> res = new HashSet<Integer>(); for(int i=0;i<nums.length;i++){ if(!res.add(nums[i])) return true; if(res.size()>k) res.remove(nums[i-k]); } return false; } }

 

这个相当于保持res集合为k大小

例子：[4,1,2,3,5,1,5]    3 

如果res里没有这个数，就往里加  4,1,2,3

这时候res.size=4>k=3 所以，要去除第一个元素4，对于i=4时的5而言，他只需要和前面1,2,3比，4已经超出k的范围了