LeetCode（5）存在重复元素3（中等）

题目描述

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。

如果存在则返回 true，不存在返回 false。

代码

class Solution {

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {

if (t < 0) return false;
int n = nums.length;

Map<Long, Long> map = new HashMap<>();
long w = (long) t + 1;

for (int i=0;i<n;i++) {

// 得到当前数的桶编号
long id = getID(nums[i], w);

// 在桶中已经存在了
if (map.containsKey(id)) {

return true;
}

// 相邻的桶中有在[num - t, num + t]内：左边相邻的桶中
if (map.containsKey(id - 1) && Math.abs(nums[i] - map.get(id - 1)) < w) {

return true;
}
//右边相邻的桶中
if (map.containsKey(id + 1) && Math.abs(nums[i] - map.get(id + 1)) < w) {

return true;
}
map.put(id, (long) nums[i]);
if (i >= k) {

map.remove(getID(nums[i - k], w));
}
}
return false;
}

public long getID(long num, long w) {

if (num >= 0) {

return num / w;
}
return (num + 1) / w - 1;
}
}

作者：Booooo_
链接：https://leetcode-cn.com/problems/contains-duplicate-iii/solution/cun-zai-zhong-fu-yuan-su-iiitong-pai-xu-w4vds/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

值注意的是：

第二个条件数组下标的范围

对于当前下标i，如果nums[i-(k+1)]产生的桶存在，我们要把其删除掉。因为abs(i-(i-(k+1))) = abs(k+1) = k+1 > k。这是不在我们下标范围内的元素产生的桶，我们不需要判断是否满足条件，直接把这个桶删除了。

LeetCode（5）存在重复元素3（中等）

原文：https://www.cnblogs.com/ash98/p/14674952.html