在数组中找出三个和的总和最接近给定数字的元素

在数组中找出三个和的总和最接近给定数字的元素

除了蛮力搜索以外，还有什么有效的算法可以找到三个整数？

是的 我们可以在O（n 2）时间内解决这个问题！首先，考虑

P

可以用稍有不同的方式等效地表述您的问题，从而消除对“目标值”的需求：

原来的问题

P

：给定一个阵列

A

的

n

整数和目标值

S

，就存在着从一个3元组

A

求和以

S

？

修改后的问题

P'

：给定一个整数数组

A

，

n

从

A

该和到零是否存在3元组？

请注意，您可以从这个版本的问题，去

P'

从

P

通过从每个元素减去你的S / 3

A

，但现在你不需要目标值了。

显然，如果仅测试所有可能的三元组，就可以解决O（n 3）中的问题-这是蛮力基准。有可能做得更好吗？如果我们以更聪明的方式选择元组怎么办？

首先，我们花一些时间对数组进行排序，这使我们付出了O（n log n）的初始代价。现在我们执行以下算法：

for (i in 1..n-2) {  j = i+1  // Start right after i.  k = n    // Start at the end of the array.  while (k >= j) {    // We got a match! All done.    if (A[i] + A[j] + A[k] == 0) return (A[i], A[j], A[k])    // We didn't match. Let's try to get a little closer:    //   If the sum was too big, decrement k.    //   If the sum was too small, increment j.    (A[i] + A[j] + A[k] > 0) ? k-- : j++  }  // When the while-loop finishes, j and k have passed each other and there's  // no more useful combinations that we can try with this i.}

该算法的工作原理是将三分，

i

，

j

，和

k

在阵列中的各个点。

i

从一开始就开始，然后慢慢地发展到最后。

k

指向最后一个元素。

j

指向

i

起点。我们迭代地尝试对元素在它们各自的索引处进行求和，并且每次发生以下情况之一：

• 总和是正确的！我们找到了答案。
• 这个数目太小了。移至

  j

  末尾以选择下一个最大的数字。
• 这个数目太大了。移动

  k

  接近开始选择下一个最小的数。

对于每一个

i

的指针

j

，并

k

会逐渐更接近对方。最终，它们将相互传递，并且在那一刻，我们不需要尝试任何其他 *** 作

i

，因为我们将以相同的顺序对相同的元素求和。在那之后，我们尝试下一个

i

并重复。

最终，我们将耗尽所有有用的可能性，或者找到解决方案。您可以看到这是O（n
2），因为我们执行了外循环O（n）次，执行了内循环O（n）次。如果您真的很喜欢，可以通过将每个整数表示为一个位向量并执行快速傅里叶变换，来进行次二次级处理，但这超出了此答案的范围。

---

注意：
因为这是一个采访问题，所以我在这里作了一些欺骗：该算法允许多次选择相同的元素。也就是说，（-1，-1，2）和（0，0，0）都是有效的解决方案。如标题所提到的，它也只找到
确切的
答案，而不是最接近的答案。作为读者的练习，我将让您弄清楚如何使其仅适用于不同的元素（但这是一个非常简单的更改）和确切的答案（这也是一个简单的更改）。