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问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。