Difficulty:easy

 More:【目录】LeetCode Java实现

Description

https://leetcode.com/problems/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 absolute difference between nums[i] and nums[j] is at most tand the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

Intuition

1. treeSet

2. bucket （future work）

 

Solution

TreeSet

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if(nums==null || k<0 || t<0)
            return false;
        TreeSet<Integer> tree = new TreeSet<>();
        for(int i=0; i<nums.length; i++){
            if(i>k)
                tree.remove(nums[i-k-1]);
            Integer ceiling = tree.ceiling(nums[i]);
            Integer floor = tree.floor(nums[i]);
            if(ceiling!=null && (long)ceiling-nums[i]<=t)
                return true;
            if(floor!=null && (long)nums[i]-floor<=t)
                return true;
            tree.add(nums[i]);
        }
        return false;
    }

　　

Complexity

TreeSet: 

　　Time complexity : O(nlog(min(n,k)))

　　Space complexity : O(min(n,k))

 

What I've learned

1. treeSet.ceiling(e) && treeSet.floor(e) 

2. Pay attention to overflow problems: difference of two values may smaller than Integer.MIN_VALUE or bigger than Integer.MAX_VALUE.

 

 More:【目录】LeetCode Java实现