arrays - 将整数数组拆分为 3 个总和相等的数字 block

Question

不知道我的措辞是否好，但我会尝试在这里进一步解释:

所以，我有一个数字数组，比方说 1 2 3 4 5 6 7 8 9 10 11 14 我需要编写一个算法将数组拆分为 3 个数字大小的数组总和相等，在本例中为:

{14,2,4} {11,6,3} {10,1,9} {5,7,8} - 我想我明白了。

所以，我现在的想法是:

检查每个可能的整数和，并将使用的三个索引和总和放入一个结构中。

然后，对于一个结构数组，我将按总和对它们进行排序，并搜索 N/3 个总和，如果找到，我将根据它们的索引打印出这些数字。

该算法包括多次遍历所有数字，因此速度会很慢。谁能建议一个更好的算法？如果有人愿意提供代码，我可以用 C 编程，我已经开始学习 Java。

谢谢!

Answer 1

你不会说你是否总是从 12 个数字开始。

您有以下数字数组:1 2 3 4 5 6 7 8 9 10 11 14

1. 数组的个数必须能被3整除，否则无解。

2. 对数字数组求和。在这种情况下，总和为 80。

3. 我们有 12 个数字，所以我们有 4 组，每组 3。将总和除以组数，即 80/4，即 20。如果此除法没有产生整数，则没有解决方案。

4. 遍历数字数组，一次三个数字，一次，并保留总和为 20 的三元组。您可以使用 12 位二进制整数，从零开始，递增 1，以选择三元组。当二进制整数有 3 个一位时，使用这些位的位置作为数字数组的索引。

5. 检查三胞胎的组数是否存在并使用数组中的所有数字。如果是这样，你有你的解决方案。如果不是，则无解。

编辑补充:原来题中给出的数字数组有4种解法:

(2,4,14); (3,6,11); (1,9,10); (5,7,8)
(2,4,14); (1,8,11); (3,7,10); (5,6,9)
(1,5,14); (3,6,11); (2,8,10); (4,7,9)
(1,5,14); (2,7,11); (4,6,10); (3,8,9)

我编写代码只是为了看看生成解决方案需要多长时间。它运行不到一秒钟。