(LeetCode) 包含重复 III

Question

给定一个整数数组，找出数组中是否有两个不同的索引 i 和 j，使得 nums[i] 和 nums[j] 之间的差最多为 t，i 和 j 之间的差最多为 k。

你好！

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

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

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

谢谢！

编辑：在此期间我也在研究这个！因此，如果我最终得到了答案，我会将其发布在这里以供将来参考。:)

Answer 1

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

以下答案基于桶，时间复杂度为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 将全部放入桶 [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 

（我们现在不必担心 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]的bucket中可能有满足要求的元素，我们需要检查一下这个。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 放入 bucket[2] 中，我们会发现其中已经有一个元素，即 6。由于一个 bucket 中的所有元素的差异都不大于 t，我们就完成了。

因此，为了检查是否有两个差值小于 t 的数字，我们将遇到的每个数字都放入一个桶中。如果该桶中已经有一个元素，那么我们就完成了。否则，我们检查相邻桶是否有满足要求的元素，如果没有，我们继续将数字放入桶中。

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

下面是我的 Python 代码。

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

Answer 2

最佳解决方案 O(n) 可以按照@Jing Zhao 的解释来完成。但是在 Java 中，您必须处理其他事情，例如整数溢出。

这是我在java中的解决方案：

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    if (nums == null || k < 0 || t < 0) return false;
    Map<Integer, Integer> buckets = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int bucket = (int) Math.floorDiv(nums[i], (long) t + 1);
        if (buckets.containsKey(bucket)) return true;
        else {
            buckets.put(bucket, nums[i]);
            // Cast to long as it overflows if 2147483647 - (-1) => -2147483648
            if (buckets.containsKey(bucket - 1) && nums[i] - (long) buckets.get(bucket - 1) <= t) return true;
            if (buckets.containsKey(bucket + 1) && buckets.get(bucket + 1) - (long) nums[i] <= t) return true;
            if (buckets.size() > k) {
                buckets.remove((int) Math.floorDiv(nums[i - k], (long) t + 1));
            }
        }
    }
    return false;
}

首先，您必须处理负数。例如，如果 nums[i] = -1 且 t = 2：

int bucket0 = -1/3 = 0 // Remember to divide by (t+1) 

这是不行的，因为它会在存储桶“0”中放置另一个数字，例如 nums[i] = 2 并且它会返回 true，因为它们在同一个存储桶中。但是 -1 和 2 之间的距离是 3 而不是 2！所以它应该返回false。处理这个问题的正确方法是使用 Math.floorDiv ：

int bucket1 = Math.floorDiv(-1,3) = -1

这会将 -1 放在存储桶“-1”中，并且应该可以正常工作。对于负数，桶会发生一点变化。这对我来说很难理解，所以我尝试更详细地解释它。

首先，我们除以 (t+1) 而不仅仅是“t”的原因如下：假设 t = 2，如果只除以“t”，那么您可以在“1”桶中得到：

2,3 // Because 2/2 and 3/2 give "1"

但是这个bucket只考虑了“1”而不是“2”的差异，例如，4也应该包括在内，因为4 - 2是2。现在如果我们除以（t+1）：

3/3,4/3,5/3 // Because all those divisions yield "1"

有了这个，我们可以确定距离“t”内的所有值，在本例中为 2，位于同一个桶内。

我们可以看到桶包含从精确除法开始的所有值，在本例中为 3/3，下一个桶“2”将从 6/3 开始。但在负数的情况下，它们将从精确除法中的多一个数字开始。这是因为 0 包含在桶 0 中。

bucket with "1" => 3,4,5
bucket with "0" => 0,1,2
bucket with "-1" => -1,-2,-3
bucket with "-2" => -4,-5,-6

如果我们在 Java 中对 -1 使用常规的 int 除法，我们将得到：

-1/3 = 0 // This would go to bucket "0"
-2/3 = 0 // This would go to bucket "0"

这是因为 Java 中的常规 int 除法只会截断，所以如果您得到 0.xxxx 的值，它将被截断为 0，或者如果您有 -1.XXX，它将被截断为 -1。但是对于 Math.floorDiv，除法将获得该值的实际下限，因此如果负值为 -1.xxxx，您将获得 -2，如果为 -1/3，则为 -1。

希望这可以帮助解决此问题的人。该解决方案非常聪明，您必须处理许多不同的边缘情况。

Answer 3

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

在内部 for 循环中检查abs(nums[i]-nums[j]) <= t 和abs(ij)<=k 的逻辑。

外循环：i从0到n

内循环：j从i+1到n