Leetcode 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.
说人话:
给定一个整数数组 nums 和一个整数 k,判断数组中是否存在两个不同的索引 i 和 j,使得 nums [i] = nums [j],并且 i 和 j 的差的绝对值 至多为 k。
示例:
[法1] 暴力法
思路
暴力法的话我们可以双层遍历 nums,找到 nums[i] = nums[j],然后再判断 j-i <= k
是否成立。
代码
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
for(int i=0;i<nums.length-1;i++){
for(int j=i+1;j<nums.length;j++){
if(nums[i] == nums[j] && j-i<=k){
return true;
}
}
}
return false;
}
}
提交结果
代码分析
- 时间复杂度:O(n2)
- 空间复杂度:O(1)
改进思路
暴力法的时间复杂度 O(n2) 还是比较大的,我们能不能扫描一遍数组就解决问题呢?因为题目要判断是否有相等的(即重复),那么我们就可以利用 Set 集合的不可重复特性还解决这个问题。又因为题目有限定 j-i <=k,所以我们又可以结合滑动窗口来解决这个问题。
[法2] 滑动窗口+查找集
思路
- 遍历数组,边遍历边把 nums[0…i-1] 的元素放到 Set 集合中
- 遍历到 nums[i] 的时候,判断 nums[0…i-1] 中是否有与 nums[i] 相等的
- 如果有,那么就返回 true
- 如果没有,就把 nums[i] 放入 Set 中
- 放入 nums[i] 后要保证 Set 中元素个数不能超过 k,如果超过 k,就把最先放入的元素 nums[i-k] 删除掉
- 如果遍历完数组后还没有找到满足条件的元素,那么就返回 false
代码
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> set = new HashSet<>();
//记录 Set 集合中元素的个数
int count = 0;
//遍历数组
for(int i=0;i<nums.length;i++){
//判断是否要满足条件的元素
if(set.contains(nums[i])){
return true;
}else{
//不满足就放入 nums[i]
set.add(nums[i]);
count++;
//检查是否越出窗口
if(count > k){
//删掉窗口最左边的元素
set.remove(nums[i-k]);
count--;
}
}
}
return false;
}
}
提交结果
代码分析
- 时间复杂度:O(n)
- 空间复杂度:O(k)