在一个数组，其总和发现三个元件是最接近给定数量的 [英] Finding three elements in an array whose sum is closest to a given number

问题描述

由于整数数组，A ₁ ，A ₂ ，...，A <子> N ，包括正片和负片，另有整数S.现在我们需要找到阵列，其总和最接近给定整S.如果存在一个以上的溶液在三个不同的整数，它们中的任何是确定

您可以假设所有的整数都int32_t范围之内，并没有算术溢出将与计算总和发生。 S是没什么特别的，但一个随机选择号码。

难道还有比蛮力搜索等找到三个整数任何有效的算法？

解决方案

  

难道还有比蛮力搜索等找到三个整数任何有效的算法？

是的;我们可以在O（N ² ）的时间解决这个问题！首先，考虑你的问题 P 可在消除了对目标值，需要一个稍微不同的方式等价措辞：

  

原题 P ：给定的数组 A N 整数和目标值取值，不存在从3元组 A 凝聚到取值？

  
  

修改问题 P'：给定一个数组 A 的<$ C $ ç> N 整数，确实存在一个三元组从 A 的总和为零？

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

显然，如果我们简单地测试所有可能的3元组，我们会解决在O问题（N ³ ） - 这是蛮力基线。是否有可能做的更好？如果我们选择的元组在一个有点更聪明的方式？

首先，我们投资一些时间到数组，其中的成本我们的O初始罚款（N log n）的排序。现在我们执行这个算法：

 的（我在1..N-2）{
  J = + 1 //后，我开始的权利。
  K =ñ//在数组的末尾开始。  而（K＆GT; = j）条{
    //我们得到了一个比赛！全做完了。
    如果（A [I] + A [J] + A [K] == 0）返回（A [I]，A [J]，A [K]）    //我们不匹配。让我们设法接近了一点：
    //如果金额过大，递减ķ。
    //如果金额过小，增加学家
    （A [I] + A [J] + A [K] 0）？ K--：J ++
  }
  //当while循环结束，J和K已通过彼此有
  //没有更多有用的组合，我们可以用这个我试试。
}
 

此算法的工作原理是将三分， I ，Ĵ和 K 在阵列中的各个点。 I 开头开始了，慢慢地工作它的方式结束。 K 指向非常最后一个元素。 Ĵ点，其中 I 已开始在。我们反复尝试在各自的指数来总结的元素，每一次发生下列情况之一：

• 的总和是完全正确的！我们已经找到了答案。


• 的总和太小。移动Ĵ更接近最终选择未来最大数量。


• 的总和太大。移动 K 接近开始选择下一个最小的数。

对于每个 I ，Ĵ和 K 将逐渐接近对方。最终，他们会互相传球，而在这一点上我们并不需要去尝试任何其他为 I ，因为我们会被总结相同的元素，只是在一个不同的顺序。在这之后，我们尝试下 I 并重复。

最后，我们会以穷尽有用的功能，否则我们将找到解决方案。你可以看到，这是O（n 2 ），因为我们执行外环O（N）次，我们执行内环O（N）次。这是可能做到这一点子二次如果你得到真正看中，通过重新presenting每个整数位向量并执行快速傅立叶变换，但这超出了这个答案的范围。

---

注意：因为这是一个面试问题，我已经被骗了一点点在这里：这种算法允许多个相同的元素的选择。即（-1，-1，2）将是一个有效的解决方案，如将（0，0，0）。它也发现只有的确切的答案，而最接近的答案，作为标题提及。作为一个练习给读者，我会让你知道如何使它只不同元素的工作（但它是一个非常简单的变化）和精确的答案（这也是一个简单的变化）。

Given an array of integers, A1, A2, ..., An, including negatives and positives, and another integer S. Now we need to find three different integers in the array, whose sum is closest to the given integer S. If there exists more than one solution, any of them is ok.

You can assume all the integers are within int32_t range, and no arithmetic overflow will occur with calculating the sum. S is nothing special but a randomly picked number.

Is there any efficient algorithm other than brute force search to find the three integers?

解决方案

Is there any efficient algorithm other than brute force search to find the three integers?

Yep; we can solve this in O(n²) time! First, consider that your problem P can be phrased equivalently in a slightly different way that eliminates the need for a "target value":

original problem P: Given an array A of n integers and a target value S, does there exist a 3-tuple from A that sums to S?

modified problem P': Given an array A of n integers, does there exist a 3-tuple from A that sums to zero?

Notice that you can go from this version of the problem P' from P by subtracting your S/3 from each element in A, but now you don't need the target value anymore.

Clearly, if we simply test all possible 3-tuples, we'd solve the problem in O(n³) -- that's the brute-force baseline. Is it possible to do better? What if we pick the tuples in a somewhat smarter way?

First, we invest some time to sort the array, which costs us an initial penalty of O(n log n). Now we execute this algorithm:

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.
}

This algorithm works by placing three pointers, i, j, and k at various points in the array. i starts off at the beginning and slowly works its way to the end. k points to the very last element. j points to where i has started at. We iteratively try to sum the elements at their respective indices, and each time one of the following happens:

• The sum is exactly right! We've found the answer.
• The sum was too small. Move j closer to the end to select the next biggest number.
• The sum was too big. Move k closer to the beginning to select the next smallest number.

For each i, the pointers of j and k will gradually get closer to each other. Eventually they will pass each other, and at that point we don't need to try anything else for that i, since we'd be summing the same elements, just in a different order. After that point, we try the next i and repeat.

Eventually, we'll either exhaust the useful possibilities, or we'll find the solution. You can see that this is O(n²) since we execute the outer loop O(n) times and we execute the inner loop O(n) times. It's possible to do this sub-quadratically if you get really fancy, by representing each integer as a bit vector and performing a fast Fourier transform, but that's beyond the scope of this answer.

---

Note: Because this is an interview question, I've cheated a little bit here: this algorithm allows the selection of the same element multiple times. That is, (-1, -1, 2) would be a valid solution, as would (0, 0, 0). It also finds only the exact answers, not the closest answer, as the title mentions. As an exercise to the reader, I'll let you figure out how to make it work with distinct elements only (but it's a very simple change) and exact answers (which is also a simple change).

这篇关于在一个数组，其总和发现三个元件是最接近给定数量的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！