相关疑难解决方法(0)

给定一个整数数组,A ₁,A ₂,...,A _n,包括负数和正数,以及另一个整数S.现在我们需要在数组中找到三个不同的整数,其总和最接近给定的整数S如果存在多个解决方案,则其中任何一个都可以.

您可以假设所有整数都在int32_t范围内,并且计算总和时不会发生算术溢出.S没什么特别的,只是随机挑选的数字.

有没有比强力搜索更有效的算法来找到三个整数？

假设我们有三个长度为N的数组,它们包含任意数量的类型long.然后给出一个数字M(相同类型),我们的任务是从每个数组中选择三个数字A,B和C(换句话说,A 应该从第一个数组中选择,B从第二个数组中选择,C从第三个数据中选择),以使之和A + B + C = M.

问题:我们可以选择所有三个数字并最终得到O(N ²)的时间复杂度吗？

插图:

数组是:

1) 6 5 8 3 9 2
2) 1 9 0 4 6 4
3) 7 8 1 5 4 3

而中号,我们已经给出是19.然后我们的选择是从第一个8,从第二个4和从第三个7.