一、leetcode算法
1、存在重复元素 II
1.1、题目
给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个不同的索引 i 和 j ，满足nums[i] == nums[j] 且abs(i - j) <= k 。如果存在，返回true ；否则，返回 false 。
示例 1：
输入：nums = [1,2,3,1], k = 3
输出：true
示例 2：
输入：nums = [1,0,1,1], k = 1
输出：true
示例 3：
输入：nums = [1,2,3,1,2,3], k = 2
输出：false
1.2、思路
思路一：此题我们可以使用hash表来解决问题，这道题有一个对应关系，就是数组的值和数组的下标有对应的关系，所以我们使用map来存储数组的值和对应的下标来使用。
1.3、答案
class Solution { public boolean containsNearbyDuplicate(int[] nums, int k) { Map<Integer,Integer> map = new HashMap<Integer,Integer>(); int length = nums.length; for(int i = 0; i < length; i++){ int num = nums[i]; //如果存在值相同，并且下标相减小于等于k if(map.containsKey(num) && i-map.get(num) <= k){ return true; } //将值和下标对应存入map中 map.put(num,i); } return false; } }
复杂度分析
时间复杂度：O(n)，其中 n 是数组 nums 的长度。需要遍历数组一次，对于每个元素，哈希表的操作时间都是 O(1)。
空间复杂度：O(n)，其中 n 是数组 nums 的长度。需要使用哈希表记录每个元素的最大下标，哈希表中的元素个数不会超过 n。
