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
}
|