2015年6月6日星期六

[LeetCode] Contains Duplicate III

Problem:
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.

Java Code:


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

没有评论:

发表评论