除了蛮力搜索以外，还有什么有效的算法可以找到三个整数？
是的 我们可以在O（n2）时间内解决这个问题！首先，考虑到您的问题P可以用稍有不同的方式等效地表达，从而消除了对“目标值”的需求：
原来的问题P：给定一个阵列A的n整数和一个目标值S，是否存在从3元组A求和以S？
修改后的问题P’：给定一个整数数组A， 从该和到零是否存在3元组？nA
请注意，您可以从这个版本的问题，去P’从P通过从每个元素减去你的S / 3 A，但现在你不需要 目标值了。
显然，如果仅测试所有可能的三元组，就可以解决O（n3）中的问题-这是蛮力基准。有可能做得更好吗？如果我们以更聪明的方式选择元组怎么办？
首先，我们花一些时间对数组进行排序，这使我们付出了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（n2），因为我们执行了外循环O（n）次，执行了内循环O（n）次。如果您真的很喜欢，可以通过将每个整数表示为一个位向量并执行快速傅里叶变换，来进行次级近似的操作，但这超出了此答案的范围。
注意：因为这是一个采访问题，所以我在这里作了一些欺骗：该算法允许多次选择相同的元素。 也就是说，（-1，-1，2）和（0，0，0）都是有效的解决方案。如标题所提到的，它也只找到确切的答案，而不是最接近的答案。作为读者的练习，我将让您弄清楚如何使其仅适用于 不同的元素（但这是一个非常简单的更改）和确切的答案（这也是一个简单的更改）。
602392714
清零编程群