用于在数组中搜索总和为一个值的 5 个元素的算法
Algorithm for searching an array for 5 elements which sum 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个整数-
如有任何帮助，我们将不胜感激。
算法：
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) + 选择的值 = 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).
[我最近问了一个类似的问题，
我需要你的帮助来解决以下问题：
我正在寻找一种算法，时间复杂度必须是ϴ( n³ )。
该算法在一个未排序的数组（n 个整数中）搜索 5 个 不同的 个整数
总和为给定的 z.
例如：对于输入：({2,5,7,6,3,4,9,8,21,10} , 22)
输出应该是true因为我们可以总结2+7+6+3+4=22
（排序其实无所谓，可以先排序数组，不影响复杂度。
所以你可以看问题好像数组已经排序了。)
-无内存限制-
-我们只知道数组元素是n个整数-
如有任何帮助，我们将不胜感激。
算法：
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) + 选择的值 = 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).