在一个已排序的数组中找到三个元素，它们的和等于第四个元素。

Question

在一个已排序的数组中找到三个元素，它们的和等于第四个元素。

13

我的一个朋友最近遇到了这个面试问题，我们觉得这个问题可以解决，但是不能在面试官认为可能的渐进时间界内完成。问题如下：

你有一个包含 N 个整数的数组 xs，已排序但可能不唯一。你的目标是找到四个数组下标 (a,b,c,d)，使得满足以下两个条件：

⁽¹⁾

xs[a] + xs[b] + xs[c] = xs[d]

a < b < c < d

目标是以O(N²)的时间复杂度完成此操作。

首先，一个O(N³log(N))的解决方案很显然：对于每个(a,b,c)有序三元组，使用二分查找来确定是否可以找到一个合适的d。现在，如何做得更好呢？

面试官提出的一个有趣的建议是将第一个条件重写为：

xs[a] + xs[b] = xs[d] - xs[c]

目前不清楚如何继续，但或许我们可以选择一个枢轴值P，并搜索加起来为P的(a,b)对和减去它的(d,c)对。对于给定的P，在数组两端向内搜索在O(n)时间内容易实现。然而，问题在于存在N²个这样的值P，而不仅仅是N个，因此实际上并没有减少问题的规模：我们正在进行O(N)次O(N²)工作。

我们发现其他地方在线讨论了一些相关问题：查找数组中加起来等于给定值的三个数字可以在N²时间内解决，但需要提前确定总和；通过迭代每个可能的总和来调整相同算法始终保持在N³。

另一个相关问题似乎是在数组中查找所有三元组之和小于或等于给定和，但我不确定那里的内容有多少相关性：一个不等式而不是一个等式会使事情变得复杂，当然，目标是固定的而不是变化的。

那么，我们缺少什么？考虑到性能要求，该问题是否不可能？还是有一个聪明的算法我们无法发现？

(1) 实际上，所提出的问题是查找所有这样的(a,b,c,d)元组，并返回它们的数量。但我认为在所需的时间限制内找到一个也已经够难了。

- amalloy

3

这样怎么样：遍历所有可能的数字对，将每个数字对的总和存储在哈希表中（键=总和，值=数字对）。然后再用相减操作在另一个哈希表中存储。最后只需要匹配键并验证数字对是否满足不等式即可。 - Zarwan

@Abhishek Bansal，建议您不要只记录单个数值，而是记录数值列表。 - Zarwan

@Zar 这可能会增加复杂度（除非有证明否则）。 - Abhishek Bansal

@Abhishek Bansal，最坏情况仍然是O(N^2)。瓶颈在于生成所有的配对。遍历哈希映射列表也无法超越这一点。最坏情况下，一个键的列表大小为N，但在这种情况下只有1个键需要遍历。仍然是O(N)。 - Zarwan

2

哦，你说得对，这确实是O(N^2)的求和。但是这并不会有什么区别。对于每个长度大于1的列表，我们要遍历的键就少一个。没有办法有超过O(N^2)个元素需要迭代。O(N^2 + N^2)仍然只是O(N^2)，所以应该没问题。@Abhishek - Zarwan

显示剩余6条评论

2个回答

3

所以一个解决方案可以是：

列出所有可能的 x[a] + x[b] 值，使得 a < b，并按照以下方式进行哈希处理

key = (x[a]+x[b]) and value = (a,b).

这一步的复杂度为O(n^2)。

现在列出所有可能的x[d] - x[c]值，其中d > c。对于每个x[d] - x[c]，通过查询哈希表中的条目来搜索。如果存在一个条目使得c > b，则我们有一个解决方案。此步骤的复杂度为O(n^2) * H。

其中H是哈希表中的搜索时间。

总复杂度为O(n^2)* H。如果数组中的值的范围较小，则H可能为O(1)。此外，哈希函数的选择取决于数组元素的属性。

- adisticated

如果您只检查一个键，则H是O(1)。搜索整个哈希映射键的成本是多少？它包含所有对=>迭代是O(n^2)... - Ray

没听懂你的意思，H 是查找时间。所以，在 map 中查找了 O(n^2) 个元素。T = O(n^2)*H。如果使用无序 map，则 H 的平均时间为 O(1)。 - adisticated

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- trincot · Accepted Answer

如果算法需要列出符合条件的解决方案（例如满足条件的a、b、c和d的集合），则最坏时间复杂度为O(n⁴)：

1. 可能有O(n⁴)种解决方案

一个简单的例子是只包含0值的数组。然后，只要它们保持顺序不变，a、b、c和d就可以随意选择。这代表了O(n⁴)种解决方案。

但更一般地说，遵循以下模式的数组具有O(n⁴)种解决方案：

w, w, w, ... x, x, x, ..., y, y, y, ...  z, z, z, ....

对于每个项目出现次数相同，并且:

w + x + y = z

然而，为了仅生成解的数量，算法可以具有更好的时间复杂度。

2. 算法

这是已发布算法的轻微变化，它不涉及因子 H。它还描述了如何处理导致相同总和的不同配置的情况。

- 检索所有对并将它们存储在数组 X 中，其中每个元素获取以下信息： a：两者中较小的索引 b：另一个索引 sum: xs[a] + xs[b] 的值 - 同时，在另一个数组 Y 中为每个这样的对存储以下内容： c：两者中较小的索引 d：另一个索引 sum：xs[d] - xs[c] 的值

上述操作的时间复杂度为 O(n²)

- 按其元素的 sum 属性对两个数组进行排序。如果 sum 值相等，则排序顺序将按如下确定：对于 X 数组，增加 b；对于 Y 数组，减少 c。排序可在 O(n²logn) 的时间内完成。 - 一起遍历两个数组以查找相等的总和对。如果是这种情况，则需要检查 X[i].b < Y[j].c。如果是这样，它代表一个解。但可能会有许多解决方案，并且在可以接受的时间内计算这些解决方案需要特别注意。

让 m = n(n-1)/2，即数组 X 的元素数（也是数组 Y 的大小）：

    i = 0
    j = 0
    while i < m and j < m:
        if X[i].sum < Y[j].sum:
            i = i + 1
        elif X[i].sum > Y[j].sum:
            j = j + 1
        else:
            # We have a solution. Need to count all others that have same sums in X and Y.
            # Find last match in Y and set k as index to it:
            countY = 0
            while k < m and X[i].sum == Y[j].sum and X[i].b < Y[j].c:
                countY = countY + 1
                j = j + 1
            k = j - 1
            # add chunks to `count`:
            while i < m and countY >= 0 and X[i].sum == Y[k].sum:
                while countY >= 0 and X[i].b >= Y[k].c:
                    countY = countY - 1
                    k = k - 1
                count = count + countY
                i = i + 1

请注意，尽管有嵌套循环，变量i和j只增加不减少。变量k总是在最内层循环中递减。虽然它也从更高的值开始，但通过k索引，它永远不能超过一个常数次访问相同的Y元素，因为在递减此索引时，它保持在Y的“相同和”范围内。

因此，这意味着算法的最后一部分运行时间为O(m)，即O(n²)。由于我的最新编辑确认排序步骤不是O(n²)，因此该步骤决定了整体时间复杂度：O(n²logn)。