查找数组中的三个元素，其总和最接近给定数字

Question

查找数组中的三个元素，其总和最接近给定数字给定一个整数数组，A 1，A 2，...，A n，包括负数和正数，以及另一个整数S.现在我们需要在数组中找到三个不同的整数，其总和最接近给定的整数S如果存在多个解决方案，则其中任何一个都可以。您可以假设所有整数都在int32_t范围内，并且计算总和时不会发生算术溢出。S没什么特别的，只是随机挑选的数字。有没有比强力搜索更有效的算法来找到三个整数？

Answer 1

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

是的; 我们可以在O（n ²）时间内解决这个问题！首先，考虑一下你的问题P可以用一种略微不同的方式来表达，从而消除了对“目标值”的需求：

原来的问题P：给定一个阵列A的n整数和目标值S，就存在着从一个3元组A求和以S？

改性问题P'：给定一个阵列A的n整数，不存在从3元组A求和为零？

请注意，您可以从这个版本的问题，去P'从P通过从每个元素减去你的S / 3 A，但现在你不需要目标值了。

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

首先，我们花费一些时间对数组进行排序，这使我们的初始惩罚为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 ²），因为我们执行外循环O（n）次，我们执行内循环O（n）次。如果您真的很喜欢，可以通过将每个整数表示为位向量并执行快速傅立叶变换来实现这种子二次方，但这超出了本答案的范围。

---

注意：因为这是一个面试问题，我在这里做了一点作弊：这个算法允许多次选择相同的元素。也就是说，（-1，-1,2）将是一个有效的解决方案，因为（0,0,0）。它也只能找到确切的答案，而不是最接近的答案，正如标题所提到的那样。作为对读者的练习，我将让你弄清楚如何使它只使用不同的元素（但这是一个非常简单的变化）和确切的答案（这也是一个简单的变化）。

Answer 2

当然这是一个更好的解决方案，因为它更容易阅读，因此不容易出错。唯一的问题是，我们需要添加几行代码以避免多个选择一个元素。

另一个O（n ^ 2）解决方案（使用hashset）。

// K is the sum that we are looking forfor i 1..n
    int s1 = K - A[i]
    for j 1..i
        int s2 = s1 - A[j]
        if (set.contains(s2))
            print the numbers
    set.add(A[i])

Answer 3

这样的事情怎么样，这是O（n ^ 2）

for(each ele in the sorted array){
    ele = arr[i] - YOUR_NUMBER;
    let front be the pointer to the front of the array;
    let rear be the pointer to the rear element of the array.;
    // till front is not greater than rear.                    
    while(front <= rear)
    {
        if(*front + *rear == ele)
        {
            print "Found triplet "<<*front<<","<<*rear<<","<<ele<<endl;
            break;
        }
        else
        {
            // sum is > ele, so we need to decrease the sum by decrementing rear pointer.
            if((*front + *rear) > ele)
                decrement rear pointer.
            // sum is < ele, so we need to increase the sum by incrementing the front pointer.
            else
                increment front pointer.
        }
    }

这会发现3个元素的总和是否与您的数字完全相等。如果你想要最接近，你可以修改它以记住最小的三角形（当前三元组的数量之间的差异），最后打印对应于最小三角形的三元组。