题目
给你一个整数数组 nums
和一个整数 k
,判断数组中是否存在两个 不同的索引 i
和 j
,满足 nums[i] == nums[j]
且 abs(i - j) <= k
。如果存在,返回 true
;否则,返回 false
。
示例1:
1 | 输入: nums = [1,2,3,1], k = 3 |
示例2:
1 | 输入: nums = [1,0,1,1], k = 1 |
示例3:
1 | 输入: nums = [1,2,3,1,2,3], k = 2 |
提示:
1 <= nums.length <= 105
-109 <= nums[i] <= 109
0 <= k <= 105
解法
解法一:
遍历数组,假设当前数字索引为i,那么计算从i+1 到i+k是否有其相同的元素,有返回true,否则继续判断下一个数字
Java
1 | public boolean containsNearbyDuplicate(int[] nums, int k) { |
解法二:
借助HashMap。
遍历数组,在遍历的过程中,判断该数字是否已经存在HashMao中了。
如果已经存在,挨个计算它之前的索引和当前索引差是否超过k,没有则返回true;
否则把当前索引加入索引列表中
1 | public boolean containsNearbyDuplicate(int[] nums, int k) { |
解法三:
使用HashSet。
遍历数组,对于每个元素做以下操作:
- 在散列表中搜索当前元素,如果找到了就返回
true
。 - 在散列表中插入当前元素。
- 如果当前散列表的大小超过了 kkk, 删除散列表中最旧的元素。
返回false
1 | public boolean containsNearbyDuplicate(int[] nums, int k) { |