在数组中查找总和最接近给定数字的三个元素 [英] Finding three elements in an array whose sum is closest to a given number

问题描述

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

Given an array of integers, A₁, A₂, ..., A_n, 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.

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

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?

是的；我们可以在 O(n²) 时间内解决这个问题！首先，考虑您的问题 P 可以用略有不同的方式等效地表述，从而消除对目标值"的需要:

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":

原始问题P:给定一个由n个整数组成的数组A和一个目标值S，是否存在来自 A 的三元组和 S 之和?

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?

修改问题P':给定一个A的n整数数组，是否存在3-来自 A 的元组总和为零?

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

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

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.

显然，如果我们简单地测试所有可能的 3 元组，我们将在 O(n³) 中解决问题——这就是蛮力基线.有没有可能做得更好?如果我们以更聪明的方式选择元组会怎样?

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?

首先，我们花一些时间对数组进行排序，这会花费我们 O(n log n) 的初始惩罚.现在我们执行这个算法:

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

这个算法的工作原理是在数组的不同点放置三个指针，i、j 和 k.i 从头开始​​，慢慢地走到最后.k 指向最后一个元素.j 指向 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:

• 总和是对的！我们找到了答案.
• 金额太小.将 j 移近末尾以选择下一个最大的数字.
• 金额太大了.将 k 移近开头以选择下一个最小的数字.

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

对于每个i，j和k的指针会逐渐靠近.最终它们会互相传递，到那时我们不需要为那个 i 尝试任何其他的东西，因为我们会以不同的顺序对相同的元素求和.在那之后，我们尝试下一个 i 并重复.

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.

最终，我们要么穷尽所有有用的可能性，要么找到解决方案.你可以看到这是 O(n²) 因为我们执行了 O(n) 次外循环，我们执行了 O(n) 次内循环.如果您真的很喜欢，可以通过将每个整数表示为位向量并执行快速傅立叶变换来按二次方方式执行此操作，但这超出了本答案的范围.

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.

注意:因为这是一个面试问题，所以我在这里作弊了一点:这个算法允许多次选择相同的元素.也就是说， (-1, -1, 2) 将是一个有效的解决方案，就像 (0, 0, 0) 一样.它也只找到精确的答案，而不是最接近的答案，正如标题所提到的.作为对读者的练习，我将让您弄清楚如何仅使用不同的元素(但这是一个非常简单的更改)和准确的答案(这也是一个简单的更改).

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屋！