package LeetCode;

import java.util.TreeSet;

public class LeetCode220 {

    // 220. Contains Duplicate III
    // https://leetcode.com/problems/contains-duplicate-iii/description/
    // 时间复杂度: O(nlogk)
    // 空间复杂度: O(k)

    public static boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {

        // 这个问题的测试数据在使用int进行加减运算时会溢出
        // 所以使用long long
        TreeSet<Long> record = new TreeSet<Long>();

        // nums = [1,2,3,1], k = 3, t = 0  true
        // nums = [1,5,9,1,5,9], k = 2, t = 3 false

        for (int i = 0; i < nums.length; i++) {

            // ceiling 向上取整,ceiling会去查找在set中有没有该值，如果没有--->null
            if (record.ceiling((long) nums[i] - (long) t) != null &&
                    record.ceiling((long) nums[i] - (long) t) <= (long) nums[i] + (long) t)
                return true;

            record.add((long) nums[i]);

            if (record.size() == k + 1)
                record.remove((long) nums[i - k]);
        }

        return false;
    }

    public static void main(String[] args) {
        int[] nums = {1, 3, 2, 1};

        int k = 3, t = 0;

        containsNearbyAlmostDuplicate(nums, k, t);

    }
}