[LeetCode]Ar219. 存在重复元素 II

🚩传送门：https://leetcode-cn.com/problems/contains-duplicate-ii/

题目

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

示例 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. 二分搜索和散列表。

解题思路一：线性搜索（超时）

思路：将每个元素与它之前的 _k_ 个元素中比较查看它们是否相等。

这个算法维护了一个 _k_ 大小的滑动窗口，然后在这个窗口里面搜索是否存在跟当前元素相等的元素。

复杂度分析

时间复杂度：，

每次搜索都要花费 的时间，哪怕 比 大，一次搜索中也只需比较 次。

空间复杂度：

官方代码

public boolean containsNearbyDuplicate(int[] nums, int k) {
    //依次遍历元素
    for (int i = 0; i < nums.length; ++i) {
        //依次遍历 k 个滑动窗口
        for (int j = Math.max(i - k, 0); j < i; ++j) {
            if (nums[i] == nums[j]) return true;
        }
    }
    return false;
}
// Time Limit Exceeded.

解题思路二：二叉搜索树（超时）

思路：通过自平衡二叉搜索树来维护一个 _k_ 大小的滑动窗口。

算法：
这个方法的核心在于降低 解法一 中搜索前 _k_ 个元素所耗费的时间。
可以想一下，我们能不能用一个更复杂的 数据结构 来维持这个 _**k**_ 大小的滑动窗口内元素的 有序性 呢？

考虑到滑动窗口内元素是严格遵守 先进先出 的，那么队列会是一个非常自然就能想到的数据结构。链表实现的队列可以支持在常数时间内的 删除，插入，然而 搜索 耗费的时间却是线性的，所以如果用队列来实现的话结果并不会比方法一更好。

一个更好的选择是使用 自平衡二叉搜索树（BST) 。 BST 中搜索，删除，插入都可以保持 _O_(log_k_) 的时间复杂度，其中 k 是 BST 中元素的个数。

在大部分面试中你都不需要自己去实现一个 BST，所以把 BST 当成一个 黑盒子 就可以了。大部分的编程语言都会在标准库里面提供这些常见的数据结构。在 Java 里，你可以用 TreeSet 或者是 TreeMap。在 C++ STL 里面，你可以用 std::set 或者是 std::map。

假设你已经有了这样一个数据结构，伪代码是这样的：

• 遍历数组，对于每个元素做以下操作：
  • 在 BST 中搜索当前元素，如果找到了就返回 true。
  • 在 BST 中插入当前元素。
  • 如果当前 BST 的大小超过了 k，删除当前 BST 中最旧的元素。
• 返回 false。

注意事项 这个算法在 _n_ 和 k 很大的时候依旧会超时。

复杂度分析

时间复杂度：，

我们会做 次 搜索，删除，插入 操作。每次操作将耗费对数时间，即为 。
注意，虽然 可以比 大，但滑动窗口大小不会超过 。

空间复杂度：

只有滑动窗口需要开辟额外的空间，而滑动窗口的大小不会超过 。

官方代码

public boolean containsNearbyDuplicate(int[] nums, int k) {
    //set集合,内部使用BST结构实现
    Set<Integer> set = new TreeSet<>();
    //依次遍历数组,将数加入set中
    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]);
        }
    }
    return false;
}
// Time Limit Exceeded.

解题思路二：散列表（通过）

用散列表来维护这个 大小的滑动窗口。

之前的方法中，我们知道了 对数时间 复杂度的 搜索 操作是不够的。在这个方法里面，我们需要一个支持在常量时间内完成 搜索，删除，插入 操作的数据结构，那就是 散列表 。

• 遍历数组，对于每个元素做以下操作：
  • 在 散列表 中搜索当前元素，如果找到了就返回 true。
  • 在 散列表 中插入当前元素。
  • 如果当前 散列表 的大小超过了 k，删除当前 散列表 中最旧的元素。
• 返回 false。

复杂度分析

时间复杂度：，

我们会做 次 搜索，删除，插入 操作。每次操作都耗费常数时间。

空间复杂度：

开辟的额外空间取决于散列表中存储的元素的个数，而滑动窗口的大小不会超过 。

官方代码

public boolean containsNearbyDuplicate(int[] nums, int k) {
    //set集合,内部使用哈希表结构实现
    Set<Integer> set = new HashSet<>();
    //依次遍历数组,将数加入set中
    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]);
        }
    }
    return false;
}