1.算法题目
给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 ķ。
示例 1:
输入: nums = [1,2,3,1], k = 3, t = 0
输出: true
示例 2:
输入: nums = [1,0,1,1], k = 1, t = 2
输出: true
示例 3:
输入: nums = [1,5,9,1,5,9], k = 2, t = 3
输出: false
2.算法思路
算法思路：根据Java实现每日一道算法面试题（10）：leecode219：存在重复元素 II的算法思路可以判断数组中是否存在 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k，问题 III 是要查找的是是否存在 nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 ķ。因此可以借鉴桶排序的思想将数据放到容量为 t 的桶内，将桶的索引和不重复的 nums[i] 插入 HashMap中，判断是否存在重复数据的步骤：
- 根据当前数据 nums[i] 计算相应的桶索引 index，在定义的 hashMap 中查找是否存在该索引的key，若存在则存在满足题意的重复元素，返回 true；若不存在进入步骤2；
- 在 hashMap 中查找是否存在比 index 小1的索引的key，若存在则比较对应的值与 nums[i] 的差值的绝对值是否小于等于 t，若小于等于 t，则返回 true；否则进入步骤3；
- 在 hashMap 中查找是否存在比 index 大1的索引的key，若存在则比较对应的值与 nums[i] 的差值的绝对值是否小于等于 t，若小于等于 t，则返回 true；否则进入步骤4；
- 将 index 和 nums[i] 插入到定义的 hashMap 中，并判断插入后 hashMap 的大小是否大于k，若大于则删除 hashMap 中最先插入的数据；若不大于则继续遍历数组；
3.算法代码
算法代码：根据算法思想编写的算法代码如下：
// 220存在重复元素 III
public static boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (t < 0) {
return false;
}
Map<Long, Long> map = new HashMap<>();
long w = t + 1; // 桶容量，比 t 大1
for (int i = 0; i < nums.length; i ++) {
long index = getBucketIndex(nums[i], w);
if (map.containsKey(index)) {
return true;
}
if (map.containsKey(index - 1) && (Math.abs(nums[i] - map.get(index - 1)) < w)) {
return true;
}
if (map.containsKey(index + 1) && (Math.abs(nums[i] - map.get(index + 1)) < w)) {
return true;
}
map.put(index, (long) nums[i]);
if (map.size() > k) {
map.remove(getBucketIndex(nums[i - k], w));
}
}
return false;
}
// 获取指定值在桶中的位置索引
public static long getBucketIndex(int x, long w) {
return x < 0 ? (x + 1) / w - 1 : x / w;
}
4.总结
桶排序是将待排序集合中处于同一个值域的元素存入同一个桶中，也就是根据元素值特性将集合拆分为多个区域，则拆分后形成的多个桶，从值域上看是处于有序状态的。对每个桶中元素进行排序，则所有桶中元素构成的集合是已排序的。
本题的算法思路很好的结合了哈希值和桶排序的思想，极大的降低了算法复杂度。
如果你有疑问或更好的算法思路，欢迎留言交流！！！
如果感觉我的文章对您有所帮助，麻烦动动小手给个喜欢，谢谢！！！
