arrays - 用于在数组中搜索总和为一个值的 5 个元素的算法

[我最近问了一个类似的问题， Search unsorted array for 3 elements which sums to a value 并得到了很好的答案，谢谢大家！:)]

我需要您的帮助来解决以下问题：
我正在寻找一种算法，时间复杂度必须是 ϴ( n³ )。

该算法在一个未排序的数组（n 个整数）中搜索 5 个不同的整数
，它们的总和为给定的z。

例如：对于输入：({2,5,7,6,3,4,9,8,21,10} , 22)

输出应该是true因为我们可以总结 2+7+6+3+4=22

（排序并不重要。可以先对数组进行排序，而不影响复杂性。

因此，您可以将问题视为数组已经排序。）

-没有内存限制-

-我们只知道数组元素是n个整数。-

任何帮助都将不胜感激。

标签： arraysalgorithmsearchtime-complexitybig-o

算法：

1）生成一个由成对的初始整数组成的数组并对其进行排序。该步骤将花费 O(n^2 * log (n^2)) 时间。

2) 从初始数组中选择一个值。O(n) 种方式。

3）现在你有一个与链接问题非常相似的问题。您必须选择两对，使它们的总和等于 z - 选择的值。谢天谢地，你有一个长度为 O(n^2) 的所有对的数组，已经排序。找到这样的对应该很简单——你在 3 整数和问题中所做的事情是一样的。您制作两个指针并总共移动它们 O(n^2) 次。

O(n^3) 总复杂度。

在查找包含您选择的值的对时，您可能会遇到一些问题。跳过包含您选择的值的每一对（当您到达这样的一对时，只需将指针进一步移动，就像它从未存在过一样）。

假设您有两对 p1 和 p2，这样 sum(p1) + sum(p2) + selected value = z。如果 p1 和 p2 中的所有整数都不同，那么您就有了解决方案。如果没有，那就是它变得有点混乱的地方。

让我们修复 p1 并检查 p2 之后的下一个值。它可能与 p2 具有相同的和，因为两个不同的对可以具有相同的和。如果是这样，肯定不会与 p1 发生与 p2 相同的碰撞，但您可能会与 p1 的另一个整数发生碰撞。如果是这样，检查p2之后的第二个值，如果它也有相同的和——它肯定不会和p1发生任何冲突。

因此，假设至少有 3 对与 p1 或 p2 具有相同的总和，您将始终找到一个解决方案，检查固定 p1 的 3 个值或检查固定 p2 的 3 个值。

剩下的唯一可能性是与 p1 相同的对少于 3 对，与 p2 相同的对少于 3 对。您最多可以通过 4 种方式选择它们——只需检查每种可能性。

这有点令人不快，但在不断的操作中，您可以处理此类问题。这意味着总复杂度为 O(n^3)。