219. 存在重复元素 II

1.题目

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

示例：

输入: nums = [1,2,3,1], k = 3
输出: true
输入: nums = [1,0,1,1], k = 1
输出: true
输入: nums = [1,2,3,1,2,3], k = 2
输出: false

2.思路

这里先给出两种方式，这两种方式会超时，但是也是可以得到结果的

    //线性搜索(超时)
    public boolean containsNearbyDuplicate1(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;
    }

线性搜索的思路就是维护了一个 k 大小的滑动窗口，然后在这个窗口里面搜索是否存在跟当前元素相等的元素

    //二叉搜索树(超时)
    public boolean containsNearbyDuplicate2(int[] nums, int k) {
        Set<Integer> set = new TreeSet<>();
        for (int i = 0; i < nums.length; ++i) {
            if (set.contains(nums[i])) {
                return true;
            }
            set.add(nums[i]);
            if (set.size() > k) {
                set.remove(nums[i - k]);
            }
        }
        return false;
    }

• 在 BST 中搜索当前元素，如果找到了就返回 true。
• 在 BST 中插入当前元素。
• 如果当前 BST 的大小超过了 kk，删除当前 BST 中最旧的元素。

最后一种，利用哈希表来做，实现与二叉搜索树是一样的

    //哈希表
    public boolean containsNearbyDuplicate2(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) {
                set.remove(nums[i - k]);
            }
        }
        return false;
    }

那么为什么实现是一样的，两者用的时间却不一样呢？

我们这里列一下TreeSet与HashSet的区别

HashSet：
不能保证元素的排列顺序，顺序有可能发生变化
集合元素可以是null,但只能放入一个null
HashSet底层是采用HashMap实现的
HashSet底层是哈希表实现的（查找、删除快，添加慢）

TreeSet：
Treeset中的数据是排好序的，不允许放入null值。
TreeSet是通过TreeMap实现的,只不过Set用的只是Map的key。
TreeSet的底层实现是采用二叉树（红-黑树）的数据结构。