leetcode 219. 存在重复元素 II（规定步长）

题目

思路 1

在 hashmap 里面挂一个链表，复杂度比较高，后面有优化版本

import java.util.ArrayList; import java.util.HashMap; import java.util.LinkedList;class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {HashMap<Integer, ArrayList<Integer>> hashMap = new HashMap<>(); // 在 hashmap 里面挂一个链表，存放所有相同元素的位置for (int i = 0; i < nums.length; i++) {if (hashMap.containsKey(nums[i])) {int size = hashMap.get(nums[i]).size();for (int j = 0; j < size; j++) {ArrayList<Integer> list = hashMap.get(nums[i]);if (Math.abs(list.get(j) - i) <= k) {System.out.println(list);System.out.println(list.get(j));return true;} else {list.add(i);}}} else {ArrayList<Integer> list = new ArrayList<>();list.add(i);hashMap.put(nums[i], list);}}return false;} }

思路 2

其实没有必要在 hashmap 里面挂一个链表，因为数组是被顺序遍历的，因此只需要记录最后一次出现的位置（最大的index）即可。

import java.util.HashMap;class Solution {public boolean containsNearbyDuplicate(int[] nums, int k) {HashMap<Integer, Integer> hashMap = new HashMap<>();for (int i = 0; i < nums.length; i++) {if (hashMap.containsKey(nums[i])) {if (Math.abs(hashMap.get(nums[i]) - i) <= k) {return true;} else { // 只需要记录最后一次出现的位置即可hashMap.put(nums[i], i); // put: 无则添加，有则覆盖}} else {hashMap.put(nums[i], i);}}return false;} }

总结

以上是生活随笔为你收集整理的leetcode 219. 存在重复元素 II（规定步长）的全部内容，希望文章能够帮你解决所遇到的问题。

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