java - (LeetCode) 包含 Duplicate III

Question

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

您好!

老实说，我有点被这个问题难住了。 (LeetCode) 讨论论坛中针对此问题提供的解决方案并未提供太多关于如何解决该问题的解释/思考过程。我宁愿完全理解解决问题的技术，也不愿得到完整的实现代码。我觉得这将是最好的学习方式。

所以，这里的线索是使用 (Java) TreeSet 来解决这个问题。我假设 floor 和 ceiling 方法在这里很有用。

如果有人能给我一点线索/提示来解决这个问题，我将不胜感激。也欢迎使用伪代码!我不需要我之前说过的完整实现代码。只是一个起点会很棒! :)

谢谢!

编辑:我同时也在研究这个!所以，如果我最终得到答案，我会把它贴在这里以供将来引用。 :)

Answer 1

这个问题已经很老了，但是 OP 仍然没有发布他/她的答案......
我会尝试向同样偶然发现这个问题的人解释。

下面的答案是基于buckets的，时间复杂度是O(n)。

基本思路是使用宽度为k的滑动窗口。我们的注意力将被限制在这个窗口中，使得这个窗口中 i 和 j(索引)之间的差异不能大于 k。 并且我们检查这个窗口中是否有两个数字相差至多为t。如果有这样的数字，那么我们就完成了。否则，我们的窗口将向前移动一步，我们将再次检查。

现在真正的问题是我们如何检查窗口中是否有两个这样的数字。当然我们可以用蛮力，那就是O(K^2)，那么整个算法就是O(n * K^2)。如果 K 不大，我们可以接受。

但是，通过使用桶，我们可以做得更好!

每当我们在窗口中遇到一个数字时，我们将它除以 (t+1)。假设结果是B，我们就把这个数放到bucket[B]中。

如果t = 3，那么0,1,2,3会全部放入bucket[0]，4,5,6,7会放入bucket[1]，8,9,10, 11 将被放入 bucket[2] 中，依此类推。我们保证一个桶中的所有数字的差异不会大于 t。还有一件事:4 - 2 = 2 < 3 并且它们在不同的桶中。是的，一些差值小于t的数可能会被分到不同的桶中。 然而，在这种情况下，它们只能在相邻的桶中。

下面是一个例子:

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

(我们现在不必担心 k，因为它与 nums 的长度相同。)

因为 t = 2，所以每当我们在列表中遇到一个数字时，我们将它除以 t+1(使用整数除法)并将其放入相应的桶中。

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

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

由于相邻bucket[1]的buckets中可能有满足要求的元素，我们需要检查一下。 bucket[0] 的编号为 1，但是 5 - 1 > 3 并且还没有 bucket[2]，所以我们继续。

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

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

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

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

如果我们继续将 8 放入 bucket[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