数组篇 (简单)十五
219. 存在重复元素 II
给定一个整数数组和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的绝对值最大为 k。(不大于k)
示例 1:
输入: nums = [1,2,3,1], k = 3
输出: true
方法一:暴力循环
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
for(int i=0;i<nums.length;i++)
for(int j=(i+1);j<nums.length;j++)
if(nums[i]==nums[j]&&Math.abs(i-j)<=k)
return true;
return false;
}
}
但是暴力循环同样有高下之分,题解的暴力循环就要比我的无脑循环更省时,利用一个滑动窗口。
注意j的边界,最大循环至j<i,因为如果存在下标比i更大的符合要求的元素,那么i迟早会循环到,而不需要j去判断
public boolean containsNearbyDuplicate(int[] nums, int k) {
for (int i = 0; i < nums.length; ++i) {
for (int j = Math.max(i - k, 0); j < i; ++j) {
if (nums[i] == nums[j]) return true;
}
}
return false;
}
方法二:哈希表查询,空间换时间
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; ++i)
{
if (set.contains(nums[i]))
return true;
set.add(nums[i]);
if (set.size() > k) 当哈希表的长度比K还大时,需要把之前的数据一个个删掉,
set.remove(nums[i - k]); 因为有可能存在相同数字,但下标已经超过了K
}
return false;
}
}