leetcode-go/leetcode/medium/220.contains-duplicate-iii.go

import (
	"math"
)

func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
	if t < 0 || k <= 0 {
		return false
	}
	// Bucket sort. |a - b| <= t => |a/t - b/t| <= 1 => |floor(a/t) - floor(b/t)| <= 1,
	// we use t to split the nums into several buckets. Given key = floor(nums[i]/t), then
	// next number which meets the condiction is in [key-1, key+1].
	// When key1 == key2, the condiction is met; if |key1 - key2| == 1, we have to double
	// check the condiction is met or not. Maintain a k length map to ensure |i - j| <= k.
	bucket := make(map[int]int)
	gap := t
	if gap == 0 {
		gap = 1
	}
	for i := range nums {
		key := int(math.Floor(float64(nums[i]) / float64(gap))) // Return the floor of x/y
		if _, ok := bucket[key]; ok {
			return true
		}
		if n, ok := bucket[key-1]; ok && abs(nums[i]-n) <= t {
			return true
		}
		if n, ok := bucket[key+1]; ok && abs(nums[i]-n) <= t {
			return true
		}
		bucket[key] = nums[i]
		if k <= i {
			delete(bucket, nums[i-k]/gap)
		}
	}
	return false
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}