220.存在重复的元素Ⅲ

题目描述

题解

BST

这道题第一印象是使用滑动窗口, 但是真正做起来会发现由于窗口中的数组不是有序的, 依然要逐个遍历比较, 这就跟暴力解法一样了.

如何保证在一个区间内有序呢, 答案是采用平衡二叉树.

维护一个大小为K的二叉搜索树, 遍历数组时在树中寻找比它大的最小数和比它小的最大数, 如果满足条件, 就直接返回true

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    TreeSet<Integer> set = new TreeSet<>();
    for (int i = 0; i < nums.length; i++) {
        Integer s = set.ceiling(nums[i]);
        if (s != null && s <= nums[i] + t) {
            return true;
        }

        Integer g = set.floor(nums[i]);
        if (g != null && nums[i] <= t + g) {
            return true;
        }

        set.add(nums[i]);
        if (set.size() > k) {
            set.remove(nums[i - k]);
        }

    }
    return false;
}