Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | 11x 3x 8x 32x 8x 24x 24x 24x 3x 21x 2x 19x 1x 18x 18x 8x 2x | export default function containsNearbyAlmostDuplicate(
nums: number[],
k: number,
t: number,
): boolean {
if (nums.length < 2)
return false
const getBucket = (num: number, distance: number) => {
return num < 0
? Math.floor((num + 1) / distance) - 1
: Math.floor(num / distance)
}
for (let i = 0, map = new Map<number, number>(); i < nums.length; i++) {
const num = nums[i]
const bucket = getBucket(num, t + 1)
if (map.has(bucket))
return true
if (
map.has(bucket - 1)
&& Math.abs(num - (map.get(bucket - 1) as number)) <= t
) {
return true
}
if (
map.has(bucket + 1)
&& Math.abs(num - (map.get(bucket + 1) as number)) <= t
) {
return true
}
// Every bucket has at most one element due to line 18.
map.set(bucket, num)
if (i >= k)
map.delete(getBucket(nums[i - k], t + 1))
}
return false
}
|