Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

1
2

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:

1
2

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:

1
2

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

• 使用hashmap来保存t个数
• 将每个数模(t+1)，将其放入对应的bucket中，那么每个bucket中的number的index差可定是在0-t之间的。
• 对于相邻的两个bucket，也可能存在index差在0-t的number，一次，对于每个相邻的bucket，需要检查是否index差小于t
• nums[i]可能是负数，若负数模(t+1)，对应的bucket会错位，因此，nums[i]需要将其全部转换为正数，即nums[i]-Integer.MIN_VALUE;
• 控制hashmap的item数目，来保证所求的index距离小于等于k
• Corner case是k<1 || t < 0

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

class