linear-list/array/contains-duplicate-iii

Contains Duplicate III

描述

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

分析

这一题比 "Contains Duplicate II" 有多了个条件，难度陡然就增大了。

对于数组内的一个整数，如果能方便的求出大于它的最小整数和小于它的最大整数，那么我们就可以判断差值是否大于t。能方便的求出最大下限和最小上限，最先想到的数据结构是二叉搜索树 BST，因为左孩子就是最大下限，右孩子就是最小上限。

可以用一个大小为 k 的滑动窗口，将窗口内的元素组织成一个 BST，每次向前滑动一步，添加一个新元素，同时删除一个最老的元素，如此不断向前滑动，不断更新 BST。如果 BST 内部有两个元素差值大于t，则返回 true，如果直到扫描完数组，BST 里都没有出现差值大于 k 的两个数，则返回 false。

对于 BST 数据结构，可以用现成的，C++里是multiset，Java 里是TreeSet。

代码 滑动窗口+BST

// Contains Duplicate III
// Time Complexity: O(nlogk), Space Complexity: O(k)
public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (k < 1 || t < 0) return false;

        final TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            final int x = nums[i];
            final Integer floor = set.floor(x);
            final Integer ceiling = set.ceiling(x);

            if ((floor != null && x <= floor + t)
                    || (ceiling != null && x >= ceiling -t))
                return true;

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

        return false;
    }
}