java - 在 n^2*log(n) 时间内有 4 个数字的 3sum 的变体？

Question

我正在为我参加的算法类(class)做一个项目，但我完全陷入了僵局。作业是在 O(n^2*log(n)) 时间内找到数组中所有 4 个数字的集合，其中 i+j=k+l。

我知道这类似于 3sum 问题，您必须在其中找到 i+j+k=0 的数组中的所有集合。我们在讲座中讨论了这个问题的解决方案，通过遍历所有唯一的 2 对(n^2 时间)并在排序数组上使用二进制搜索，在 O(n^2*log(n)) 时间内解决了这个问题找到满足问题的值(log(n) 时间)。

但是，这次我没有看到如何解决 4 个数字的问题。我认为可以安全地猜测复杂度中的 log(n) 来自二进制搜索，我将在最后一个搜索中使用它。但是，这意味着我必须在 n^2 时间内迭代 3 的所有可能组合，我认为这是不可能的。

我不是在找人为我做我的工作，但也许如果有人知道如何解决这个问题，他们可以在正确的方向上轻轻敲击我。谢谢。

编辑:注意我需要使用排序来解决这个问题可能也会有所帮助。一旦我这样做了，我就必须编写另一个实现来使用散列来使其更快，但我认为我自己就能做到这一点。我只需要弄清楚如何先解决排序问题。

Answer 1

保留一个排序的总和和对列表。例如，给定列表

[1, 2, 4, 8, 16, 32, 9, 82]

我们要识别1+9 = 2+8

找出列表中最大的两个数，O**(N)**。在这种情况下，它们是 (82, 32)，总和为 114。分配一个包含 114 个位置的数组 pair_sum；将所有位置设置为空指针。

现在遍历列表中的 i、j 对。对于每一对，在索引 i+j 处插入两个数字作为元组值。当您在某个索引处发生碰撞时，您就完成了:您找到了第二个对和。

我将在一些不太伪的代码中对此进行概述；您可以翻译成您最喜欢的实现语言。

银行 = [1, 2, 4, 8, 16, 32, 9, 82] 大小=长度(银行)

// Find the two largest numbers and allocate the array ...
pair_sum = array[114], initialize to all nulls

for lo in 0:size-1
    for hi in lo+1:size
        sum = bank[lo] + bank[hi]
        if pair_sum[sum]
            // There is already a pair with that sum
            print pair_sum[sum], "and", bank[lo], bank[hi]
        else
            // Record new sum pair
            pair_sum[sum] = tuple(bank[lo], bank[hi])

这是 O(N^2)，有界空间取决于数组值。

如果您出于实际原因不允许将总和用作索引，我认为您可以将其调整为二进制搜索和插入，从而为您提供 log(n) 组件。