我正在为我的校园安置做准备。我遇到一个问题，它像这样：
给定3个数组，例如
array 1: {2,1,4,7}
array 2: {3,-3,-8,0}
array 3: {-1,-4,-7,6}
我们必须从每个数组中提取一个数字并形成三元组，以使三元组中的数字总和为0，或者为该事实的任何数字。
例如，对于上述情况，解决方案之一可以是 {2, -8, 6}
目前，除了“蛮力”方法以外，我还没有其他解决方案需要花费O(n^3)时间。如何在较短的时间内做到这一点？
提前致谢。
您可以在O（n ^ 2）中进行操作：
第二个或第三个数组的增量索引，取决于和是负数还是正数。
// Asssume array2 and array3 are sorted as mentioned above
// array2: {-8,-3,0,3}
// array3: {6,-1,-4,-7}
foreach (e1 in array1)
{
int i2 = 0;
int i3 = 0;
while (i2 < array2.Length && i3 < array3.Length)
{
int sum = e1 + array2[i2] + array3[i3];
if (sum == 0) Console.WriteLine( e1, array2[i2], array3[i3]);
if (sum < 0) ++i2 else ++i3;
}
}
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句