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

  • Z时代
  • 2024-01-10
  • 分类：问答

给定一个整数数组A 1，A 2，…，A

n，包括负数和正数，以及另一个整数S。现在我们需要在数组中找到三个不同的整数，它们的和最接近给定的整数S如果存在多个解决方案，那么任何一个都可以。

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

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

回答：

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

是的 我们可以在O（n 2）时间内解决这个问题！首先，考虑P可以用稍有不同的方式等效地表述您的问题，从而消除对“目标值”的需求：

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

给定一个整数数组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）都是有效的解决方案。如标题所提到的，它也只找到

确切的

答案，而不是最接近的答案。作为读者的练习，我将让您弄清楚如何使其仅适用于不同的元素（但这是一个非常简单的更改）和确切的答案（这也是一个简单的更改）。

以上是 在数组中找出三个和的总和最接近给定数字的元素 的全部内容， 来源链接： utcz.com/qa/416006.html

回到顶部