Array 219 存在重复元素滑动窗口

2020-10-23

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值至多为 k。

思路：双层循环，依次比较两个数是否相等。因为会重复比较，让第二层循环的索引从第一层索引开始，而不是0。

分情况：数组为空和只有一个元素的时候，直接返回 false。

审题不清晰：至多是小于等于的意思。也就是这道是有关长度为 k 的滑动窗口。

方法一线性搜索

public boolean containsNearbyDuplicate(int[] nums, int k) {
       // if(k < 1) system.out('')
       int len = nums.length;
       // 长度小于 2 的数组不存在重复元素
       if(len <= 1) return false;

       // 双重遍历，依次查找重复元素
       for(int i = 0;i <= len -1;i++){
           for(int j = i+1;j < len;j++){
               // 至多是小于等于的意思
               if((nums[i] == nums[j]) && (j-i <= k)) return true;
           }
       }
       return false;

   }

时间复杂度：双层循环 $O(n^2)$.

空间复杂度：仅需要常数的额外空间。

改良：内层循环，维护一个长度为 K 的滑动窗口。

for(int i =0 ;i < len -1;i++){
    # j < i , i 和 i 之前的 k 个元素进行比较
    for(int j = Math.max(0,i-k);j < i;j++){
    	if(nums[i] == nums[j]) return true;
    }
}

方法二二叉搜索树

链表实现的队列可以支持在常数时间内的 删除，插入，然而 搜索 耗费的时间却是线性的。自平衡二叉搜索树（BST) 中搜索，删除，插入都可以保持 )O(logk) 的时间复杂度，其中 k 是 BST 中元素的个数。

思路：维护元素个数为 k 的 BST。

遍历元素，在 BST 中搜索是否存在该元素
在 BST 中插入当前元素。
如果当前 BST 的大小超过了 k，删除当前 BST 中最旧的元素

时间复杂度：$O(nlog(min(k,n)))$,n 次 搜索，删除，插入 操作。每次操作将耗费对数时间，即为log(min(k,n))

空间复杂度：$O(min(n,k))$.只有滑动窗口需要开辟额外的空间，而滑动窗口的大小不会超过 O(min(n,k))。

注意事项

方法三：hashset

前面两种算法在 n 和 k 很大的时候都会超时。

在常量时间内完成 搜索，删除，插入 操作的数据结构，那就是散列表

思路：维护一个长度为 k 的哈希表。

遍历元素，判断 hashmap 是否存在该元素
将元素加入哈希表
判断哈希表的长度，如果长度大于 k，就移除第一个元素，一直保持哈希表的长度为 k。

时间复杂度：$o(n)$,n 次搜索，删除，插入操作，每个操作都耗费常数事件。

空间复杂度：$O(min(n,k))$ 开辟的额外空间取决于散列表中存储的元素的个数，也就是滑动窗口的大小。

Set<Integer> set = new HashSet<>();
for(int i = 0;i < len;i++){
    // 如果 长度 k 内找到了重复元素，直接返回
    if(set.contains(nums[i])){
    return true;
}
// 不相同，就加入 set 
set.add(nums[i]);
// 这里还没有遇到相等的元素
// set 的长度是否超过 k ，是就从头删除多余的元素
if(set.size() > k){
    set.remove(nums[i - k]);
	}
}
return false;

方法一 线性搜索

方法二 二叉搜索树

方法三：hashset

方法一线性搜索

方法二二叉搜索树