（本文给出了）包含重复III

Question

鉴于整数数组，找出是否有两个不同的 指数i和阵列以J使得NUMS之间的差[I] 和NUMS [j]为至多t，i和j之间的差值最大为 k。

您好！

老实说，我有点难倒了这个问题。在（LeetCode）讨论论坛中为这个问题提供的解决方案没有提供关于如何解决它的很多解释/思考过程。我宁愿完全理解解决问题的技巧，而不是给我全面的实现代码。我觉得这将是最好的学习方式。

因此，这里的线索是使用（Java）TreeSet来解决这个问题。我假设地板和天花板方法在这里会很有用。

我很感激，如果有人在那里可以给我一点线索/提示来解决这个问题。伪代码也是受欢迎的！我不需要像我之前说过的完整的实现代码。刚开始的时候会很棒！ :)

谢谢！

编辑：我也在此期间工作！所以，如果我最终得到答案，我会在这里发布以供将来参考。 :)

Answer 1

想到的第一个实现只是两个for循环，一个嵌套。

在inner for循环中检查abs（nums [i] -nums [j]）< = t和abs（i-j）< = k的逻辑。

外环：我从0到n

内环：J-从i + 1到n

Answer 2

的问题是很老，但仍然OP没有公布他/她的答案......
我会尝试向那些也在这个问题上无法解决的人解释。

以下回答基于存储桶，时间复杂度为O（n）。

其基本思想是使用宽度为k的滑动窗口。我们的注意力将被限制在这个窗口中，使得这个窗口中的i和j（索引）之间的差异不能大于k。 我们检查这个窗口中是否有两个数字，最多t的差值。如果有这样的数字，那么我们就完成了。否则，我们的窗口将前进一步，然后我们再次检查。

现在真正的问题是我们如何检查，如果有两个这样的数字在窗口。当然，我们可以使用残酷的力量，这将是O（K^2），那么整个算法将是O（n * K^2）。如果K不大，我们可以接受。

但是，通过使用桶，我们可以做得更好！当我们在窗口中遇到一个数字时，我们将它除以（t + 1）。假设结果是B，我们然后把这个数字放到桶[B]中。

如果t = 3，则数字0,1,2,3将全部放入存储桶[0]中，数字4,5,6,7将放入存储桶[1]中，并且存储8,9,10 ，11将被放入桶[2]等等。我们保证一个桶中的所有数字的差值不会大于t。还有一件事：4 - 2 = 2 < 3，它们在不同的桶中。是的，一些差异小于t的数字可能被放入不同的桶中。 然而，在这种情况下，他们只能在邻近的桶中。

下面是一个例子：

nums = [1, 5, 17, 6, 8], t = 2, k = 5 

（我们不必现在担心ķ，因为它是一样NUMS的长度）

由于T = 2，所以每当我们遇到列表中的一个数字，我们用t除以它+ 1（整数除法用于），并把它在对应桶。

1/3 = 0 --> We put 1 in bucket[0] 

5/3 = 1 --> We put 5 in bucket[1] 

由于有可能在桶桶邻国[1]符合要求的元素，我们需要检查这个。 bucket [0]具有数字1，但是5-1> 3并且没有bucket [2]，所以我们继续。

17/3 = 5 --> We put 17 in bucket[5] 

没有桶[4]或桶[6]，所以我们继续。

6/3 = 2 --> We put 6 in bucket[2] 

我们必须检查bucket [1]中的数字：| 5 - 6 | = 1 < 2所以有这样的数字，我们返回True。

如果我们继续把8斗[2]，我们会发现已经有中的一个元素，这是6。由于在一个桶中的所有元素都没有较大的是t，我们完成了分歧。

所以要检查是否有小于T两个数的差别，我们把我们的每一个桶中遇到的号码。如果该桶中已经有一个元素，那么我们就完成了。否则，我们检查相邻桶是否具有满足要求的元素，如果没有，我们继续将数字放入桶中。

我们几乎已经完成了。现在我们需要考虑窗口宽度k。将所有k个数字放入桶中后，如果我们没有找到两个这样的数字，我们需要将窗口向前移动一步。也就是说，要删除最左边的号码及其相应的存储区并在其存储区中添加新的号码。如果它的桶已经被拿走了，那么我们就完成了。否则，我们检查它的邻近桶，如果有的话。

下面是我的Python代码。

if t < 0 or not nums or k <= 0: 
    return False 
buckets = {} 
width = t + 1 

for n, i in enumerate(nums): 
    buck = i // width 
    if buck in buckets: 
     return True 
    else: 
     buckets[buck] = i 
     if buck - 1 in buckets and i - buckets[buck-1] <= t: 
      return True 
     if buck + 1 in buckets and buckets[buck+1] - i <= t: 
      return True 
     if n >= k: 
      del buckets[nums[n-k] // width] 
return False