algorithm - 4 求和时间复杂度

Question

这是典型的 4sum 问题。
给定一个包含 n 个整数的数组 S，S 中是否存在满足 a + b + c + d = target 的元素 a、b、c 和 d？在给出目标总和的数组中找到所有唯一的四元组。

我知道的一种解决方案将花费 O(n^3) 时间。但是当我在分析最小时间复杂度时，我对以下陈述感到困惑:“由于 4 个数字将有 O(n^4) 种组合，在最坏的情况下，它们可能全部加起来为目标数字，因此我们必须至少访问每个组合一次。因此，最小时间复杂度为 O(n^4)。”

我知道这个说法显然是错误的(毕竟存在 O(n^3) 算法)，但不知道为什么。

我知道这可能是一个愚蠢的问题......但我真的很困惑。谁能帮忙？提前致谢。

Answer 1

这是因为该问题要求给出指定总和的 4 个数字的所有唯一组合。让我们看看细节。如果引用语句

Since there will be O(n^4) kinds of combinations for 4 numbers, in the worst case they might all sum up to the target number and therefore we have to at least visit each of the combination once. As a result, minimal time complexity is O(n^4).

是真的，这意味着类似的 2-Sum 问题具有最小的时间复杂度 O(n^2)，对吗？然而，我们都知道事实并非如此。那是因为我们不必检查所有对以找到所有唯一 对。假设相反，即所有对的总和为指定的总和，并且都是唯一的，因此我们需要对它们进行全部检查。这意味着我们可以从数组中找到四个不同的整数 a, b, c, d 使得 a + b = s 和 c + d = s，还有 a + c = s 和 b + d = s。这意味着 2a + b + c = 2d + b + c，或 a = d，这给出 b = c。因此，(a,b) = (c,d)，所以所有对都是唯一的假设是错误的，这是矛盾的。因此，如果我们处理 (a,b) 对，我们可以跳过 (c,d)，因为它是同一对。这就是具有 O(n^3) 复杂度的算法在 4-Sum 问题的情况下所做的，它们通过在开始时对输入数组的元素进行排序或散列来利用这一事实。可以找到一些巧妙的解决方案 here .