题目：
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.
链接： http://leetcode.com/problems/contains-duplicate-iii/
题解：
一开始的想法是用类似Contains Duplicate II的方法，不过好像不好写。于是研究了一下Discuss，发现有大概三种解法。
最后暂时只做了第一种方法。排序以后再查找，这里需要自己定义一个数据结构，implements Comparable，并且还有一个inRangeTWith method来比较两个节点的原index是否在t范围内。 二刷一定要补上第二和第三种。
Time Complexity - O(n2) ， Space Complexity - O(n)
public class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { if(nums == null || nums.length < 2 || t < 0 || k < 0) return false; ValueWithIndex[] arr = new ValueWithIndex[nums.length]; for(int i = 0; i < nums.length; i++) arr[i] = new ValueWithIndex(nums[i], i); Arrays.sort(arr); for(int i = 0; i < arr.length; i++) { for(int j = i + 1; (j < arr.length) && (arr[j].inRangeTWith(arr[i], t)); j++) { if(Math.abs(arr[i].index - arr[j].index) <= k) return true; } } return false; } private class ValueWithIndex implements Comparable<ValueWithIndex> { public int value; public int index; public ValueWithIndex(int val, int i) { this.value = val; this.index = i; } public int compareTo(ValueWithIndex v2) { if(value < 0 && v2.value >= 0) return -1; if(value >= 0 && v2.value < 0) return 1; return value - v2.value; } public boolean inRangeTWith(ValueWithIndex v2, int t) { // value always >= v2.value if(value == v2.value) return true; if(value >= 0 && v2.value >= 0) return value - v2.value <= t; else if(value < 0 && v2.value < 0) return value <= v2.value + t; else return value - t <= v2.value; } } }
Reference:
https://leetcode.com/discuss/65056/java-python-one-pass-solution-o-n-time-o-n-space-using-buckets
https://leetcode.com/discuss/47974/java-treeset-implementation-nlogk
https://leetcode.com/discuss/52545/java-solution-without-dictionary-sort-nums-record-positions
https://leetcode.com/discuss/39216/ac-short-java-solution-using-treeset-and-subset-function
https://leetcode.com/discuss/38206/ac-o-n-solution-in-java-using-buckets-with-explanation
https://leetcode.com/discuss/38177/java-o-n-lg-k-solution
https://leetcode.com/discuss/38148/my-o-n-accepted-java-solution-using-hashmap
https://leetcode.com/discuss/38146/java-solution-with-treeset
原文：http://www.cnblogs.com/yrbbest/p/4990420.html