Duplicate问题

219. Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

我的方法：HashMap，key：每一个不同的nums[i]值， value：这个nums[i]值所对应的所有index的一个list

但是慢在先都装到map里，再对每个key做判断。

class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {if(nums == null || nums.length == 0){return false;} if(nums.length == 1){return false; }Map<Integer, List<Integer>> map = new HashMap<>(); for(int i=0; i<nums.length; i++){List<Integer> list;if(!map.containsKey(nums[i])){list= new ArrayList<>(); }else{list = map.get(nums[i]); }list.add(i);map.put(nums[i], list); }boolean result = false;for(Integer key : map.keySet()){List<Integer> valList = map.get(key);if(valList.size() != 1){int smallestDiff = getSmalleastIndexDiff(valList);if(smallestDiff <= k){result = true;break;}} }return result;}private int getSmalleastIndexDiff(List<Integer> valList){int result = Integer.MAX_VALUE;for(int i=0; i<valList.size()-1; i++){int diff = Math.abs(valList.get(i) - valList.get(i+1));result = Math.min(result, diff); }return result; } }

这个是我在leetcode讨论区看到别人的方法，一边装map的过程就可以判断,

HashMap，key：每一个不同的nums[i]值， value：这个nums[i]值所对应的最近的index

class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) { if(nums == null || nums.length == 0){return false;} Map<Integer, Integer> map = new HashMap<>(); for(int i=0; i<nums.length; i++) {if(map.containsKey(nums[i])) {if(Math.abs(i-map.get(nums[i])) <= k){return true;} else{map.put(nums[i], i); //这边需要注意}} else {map.put(nums[i], i);}}return false;} }

 

总结

以上是生活随笔为你收集整理的Duplicate问题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。