Leetcode - 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.

[balabala] 我的思路是构造一个类，其包含两个属性：值和下标。首先将原始数组转换为包装类数组，接着排序包装类数组，然后遍历有序数组检查是否有满足题意的pair。实现如Method1, 在不使用long的情况下需要对溢出做容错处理。 Method2 为网上大牛的思路（http://blog.csdn.net/xudli/article/details/46323247），很开心认识TreeSet，自己之前从没用过……

 

import java.util.SortedSet;
public class Solution {
    // Method2: 滑动窗口 + TreeSet
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null || nums.length < 2 || k < 1 || t < 0)
            return false;
        SortedSet<Long> set = new TreeSet<Long>();
        for (int i = 0; i < nums.length; i++) {
            SortedSet<Long> subset = set.subSet((long)nums[i] - t, (long)nums[i] + t + 1);
            if (!subset.isEmpty())
                return true;
            if (i >= k)
                set.remove((long)nums[i - k]);
            set.add((long)nums[i]);
        }
        return false;
    }
    
    // Method 1
    class WrappedNum{
        int value;
        int idx;
        public WrappedNum(int value, int idx) {
            this.value = value;
            this.idx = idx;
        }
    }
    class WrappedNumComparator implements Comparator {

        @Override
        public int compare(Object o1, Object o2) {
            int value1 = ((WrappedNum)o1).value;
            int value2 = ((WrappedNum)o2).value;
            if (value1 > 0 && value2 > 0 || (value1 < 0 && value2 < 0))
                return value1 - value2;
            else if (value1 > 0)
                return 1;
            else
                return -1;
        }
        
    }
    public boolean containsNearbyAlmostDuplicate1(int[] nums, int k, int t) {
        if (nums == null || nums.length < 2)
            return false;
        WrappedNum[] numsWrapped = new WrappedNum[nums.length];
        for (int i = 0; i < nums.length; i++) {
            numsWrapped[i] = new WrappedNum(nums[i], i);
        }
        Arrays.sort(numsWrapped, new WrappedNumComparator());
        for (int i = 1; i < nums.length; i++) {
            int currValue = numsWrapped[i].value;
            for (int j = i - 1; j >= 0 && (currValue - numsWrapped[j].value) >= 0 && (currValue - numsWrapped[j].value) <= t; j--) {
                if ((Math.abs(numsWrapped[i].idx - numsWrapped[j].idx)) <= k) {
                    return true;
                }
            }
        }
        return false;
    } 
}