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

// @Title: 存在重复元素 III (Contains Duplicate III)
// @Author: 15816537946@163.com
// @Date: 2021-04-17 17:58:17
// @Runtime: 24 ms
// @Memory: 6.2 MB
func getID(x, w int) int {
	if x >= 0 {
		return x / w
	}
	return (x+1)/w - 1
}

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

func containsNearbyAlmostDuplicate(nums []int, k, t int) bool {
	mp := map[int]int{}

	for i, x := range nums {
		id := getID(x, t+1)
		if _, has := mp[id]; has {
			return true
		}
		if y, has := mp[id-1]; has && abs(x-y) <= t {
			return true
		}
		if y, has := mp[id+1]; has && abs(x-y) <= t {
			return true
		}

		mp[id] = x
		if i >= k {
			delete(mp, getID(nums[i-k], t+1))
		}
	}
	return false
}