本文共 2141 字,大约阅读时间需要 7 分钟。
public class Solution { public boolean containsNearbyDuplicate(int[] nums, int k) { if(nums.length == 0||nums.length == 1) return false; int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE; for(int num:nums){ if(num < min) min = num; if(num > max) max = num; } Integer[] flag = new Integer[max - min + 1]; for(int i = 0;i < flag.length;i++){ flag[i] = null; } for(int i = 0;i < nums.length;i++){ if(flag[nums[i]-min]!=null){ if((i-flag[nums[i]-min]) <= k) return true; }else{ flag[nums[i]-min] = i; } } return false; }}
最容易想到的就是排个序,然后便利看前后是否有重复。
Setset = new HashSet (); for(int i = 0; i < nums.length; i++){ if(i > k) set.remove(nums[i-k-1]); if(!set.add(nums[i])) return true; }
一开始想用map来记录每个值和他对应的索引,当containskey以后,比较两个索引的差值,猛一看觉得没什么问题,但是你是从头到尾往map里面放的话,第一个进去了,下一次跟它重复的如果离得很远被跳过,但是之后每一个重复的数字都是在跟他们第一次出现的位置比,而不是跟他们上一次出现的位置比,所以还不如直接用set,只把k长的数据放进去,相当于每个数只跟他们前边k个数范围进行判断是否contains
也可以在第一题的基础上,第一题是对一个数组判定是否存在重复。第二题相当于一个数组的k窗口大小判定是否重复,遍历一遍窗口大小的子数组,分别用第一题进行判定
错误代码
Mapmap = new HashMap(); for(int i = 0;i < nums.length;i++){ if(map.containsKey(nums[i])){ if((i - map.get(nums[i])) <= k) return true; }else{ map.put(nums[i],i); } } return false;
转载地址:http://ihdvi.baihongyu.com/